概述
在一个已排序的数组seq中，使用二分查找v，假如这个数组的范围是[low...high]，我们要的v就在这个范围里。查找的方法是拿low到high的正中间的值，我们假设是m，来跟v相比，如果m>v，说明我们要查找的v在前数组seq的前半部，否则就在后半部。无论是在前半部还是后半部，将那部分再次折半查找，重复这个过程，知道查找到v值所在的地方。
实现二分查找可以用循环，也可以递归。
java实现
循环
public static int iterativeSearch(int v, int[] seq) {
int low = 0, high = seq.length - 1;
while (low < high) {
int mid = (low + high) / 2;
int m = seq[mid];
if (v == m) {
return mid;
} else if (v > m) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
}
递归
public static int recursionSearch(int v, int low, int high, int[] seq) {
if (low > high) return -1;
int mid = (low + high) / 2;
int m = seq[mid];
if (v == m) {
return mid;
} else if (v > m) {
return recursionSearch(v, mid + 1, high, seq);
} else {
return recursionSearch(v, low, mid - 1, seq);
}
}
｝
java8原生实现
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1; while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid]; if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
时间复杂度
比如：总共有n个元素，每次查找的区间大小就是n，n/2，n/4，…，n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O()=O(logn)