【算法学习】二分查找算法

二分查找算法用于在一列已排序的数组中找出一个数的位置。

假设下面有一列已排序的数:[a1,a2,a3,a4,...an],有a1<=a2<=a3<=a4<=...<=an

当我们要查询一个数a是否在数组中,直接的办法就是一个个比对,找到了即返回所在位置,没找到就返回-1;这种方法的时间复杂度是O(n)

设有n个数,二分查找是先找数组[1..n]中间的那个数M,设其位置为i

  1. 如果aM小,则a肯定在M的左边,下一轮查数组[1..i-1]
  2. 如果aM大,那a肯定在M的右边,下一轮查询[i+1..n]
  3. 如果a等于M,将M所在位置返回,即返回i

代码:

1. 无递归版本

    public static int isIn(int[] arr, int target) {
		int left = 0, right = arr.length-1;
		while(left<=right) {
			int mid = (left+right)/2;
			if(arr[mid]==target) {
				return mid;
			} else if(arr[mid]>target) {
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		return -1;
	}

2. 递归版本

    public static int isIn2(int[] arr, int target, int left, int right) {
		if(left<=right) {
			int mid = (left+right)/2;
			return arr[mid] == target? mid : (arr[mid]>target?isIn2(arr,target,left,mid-1):isIn2(arr,target,mid+1,right));
		}
		return -1;
	}

源码:https://github.com/zgljl2012/base-algorithms