二分查找算法用于在一列已排序的数组中找出一个数的位置。
假设下面有一列已排序的数：[a1,a2,a3,a4,...an]，有a1<=a2<=a3<=a4<=...<=an
当我们要查询一个数a是否在数组中，直接的办法就是一个个比对，找到了即返回所在位置，没找到就返回-1；这种方法的时间复杂度是O(n)。
设有n个数,二分查找是先找数组[1..n]中间的那个数M，设其位置为i
- 如果
a比M小，则a肯定在M的左边，下一轮查数组[1..i-1]； - 如果
a比M大，那a肯定在M的右边，下一轮查询[i+1..n]； - 如果
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;
}