二分法理解

2019-09-02

前言

　　二分法查找，即将数组一分为二，每次排除掉一半，在剩下的一半中进行寻找，这样子的效率是很高的。举个例子，假如我们要在1-100中找出一个特定的数字，我们可以将100一分为2，然后考虑这个数是否大于50，如果是，则我们排除掉1-50，在50-100之间继续寻找。如果不是，则我们排除掉50-100，在1-50之间继续寻找。这样我们每次都是排除掉一半，很快就会找到那个数字。正因为这样，二分法要求必须是一个有序的数组，而且当里面有多个我们要寻找的元素时，找到这个元素的位置不一定是最前面或者最后面的。

正文

1.原理

　　我们有一个经过排序的数组int nums[]，二分法查找则是找到数组中间的数nums[mid], 然后与我们要找的数key进行对比。

如果nums[mid] > key，则key可能在数组前半段，所以将数组的最大坐标设置为mid-1，然后继续在前半段寻找
如果nums[mid] < key，则key可能在数组后半段，所以将数组的最小坐标设置为mid+1，然后继续在后半段寻找
如果nums[mid] = key，则已经找到，返回即可。

2.代码

/**
 * 二分查找
 *
 * @author Harrison
 * @datetime 2019-9-2 10:17
 */
public class BinarySearch {

	public static void main(String[] args) {

		int nums[] = {1,3,8,15,26,27,39,57,69,78};
		int key = 78;
		long start = System.currentTimeMillis();
		//int index = binarySearchRecursion(nums, key, 0, nums.length - 1);
		int index = binarySearch(nums, key);
		System.out.println("查找完成， 耗时" + (System.currentTimeMillis() - start)/1000 + "秒。");
		System.out.println("查找到" + key + "的位置为:" + index);
	}

	/**
	 * while循环查找
	 *
	 * @param nums
	 * @param key
	 * @return
	 */
	public static int binarySearch(int nums[], int key){



		int high = nums.length - 1;
		int low = 0;

		while (low <= high) {

			// 中间值下标
			int mid = low + (high - low) / 2;
			/**
			 * 1.如果中间值大于key，则将最大下标high设置为中间值下标mid-1。然后再从low到mid-1中继续寻找
			 * 2.如果中间值小于key，则将最小下标low设置为中间值下标mid+1。 然后再从mid+1到high中继续寻找
			 * 3.如果中间值等于key，则寻找成功
			 */
			if(nums[mid] > key){
				high = mid - 1;
			} else if (nums[mid] < key){
				low = mid + 1;
			} else {
				return mid;
			}
		}

		// 未找到返回-1
		return -1;
	}

	/**
	 * 递归循环查找
	 *
	 * @param nums
	 * @param key
	 * @param start
	 * @param end
	 * @return
	 */
	public static int binarySearchRecursion(int nums[], int key, int start, int end) {

		if(start <= end){
			int mid = start + (end - start) / 2;
			if(nums[mid] < key){
				return binarySearchRecursion(nums, key, mid + 1, end);
			} else if (nums[mid] > key){
				return binarySearchRecursion(nums, key, start, mid - 1);
			} else {
				return mid;
			}
		}

		return -1;
	}
}

3.优缺点

　　二分法查找每次都会排除掉一半的数据，所以比全遍历的线性查找效率要高的多，但是如果数组存在多个相同元素，结果就是不确定的了。而且如果数组中存在一些不可比较的元素，比如字符串，无法根据自然顺序排序，结果也是不确定的。