二分法查找
二分搜索用于在一个单调或者局部单调有序数组中查找一个符合某些条件的值,时间复杂度为O(logN)
。
第一次查找位置为 N / 2
,第二次查找为N / 4
,后面依次为 N / 8
...
所以,查找次数的时间复杂度的大O记法可表示为 O(logN)
(以2为底)
代码示例:
在一个有序数组中,找出某个数是否存在
/**
* 在一个有序数组中,找出某个数是否存在
*/
public boolean binarySearchExist(int[] sortedArray, int num) {
if (sortedArray == null || sortedArray.length == 0) {
return false;
}
int L = 0;
int R = sortedArray.length - 1;
int mid = 0;
while (L < R) {
// mid = (L + R) / 2;
// 防止 L + R 所得的结果过大,溢出int类型最大值
// 改造
// mid = L + (R - L) / 2; // R 不会溢出,L 不会溢出, (R - L) / 2 更不会造成溢出
// 等同于
mid = L + ((R - L) >> 1);
if (sortedArray[mid] == num) {
return true;
} else if (sortedArray[mid] > num) {
R = mid;
} else {
L = mid;
}
}
return sortedArray[mid] == num;
}