二分查找多用于有序的数组,时间复杂度为 O(N)
1.有序数组查找某数
private int binarySearch(int[] arr, int value) {
//arr非空,长度判断省略
int mid, L = 0;
int R = arr.length - 1;
while (L < R) {
//计算mid, 这样写比(L+R)/2好,因为L+R时会数据溢出
mid = L + ((R - L) >> 1);
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
L = mid + 1;
} else {
R = mid - 1;
}
}
//L==R时
if (arr[L] == value) {
return L;
}
return -1;
}
2.有序数组大于等于某个数的最左位置
/**
* 二分查找 大于等于 某个数的最左index
*/
private int binarySearchLeft(int[] arr, int value) {
//arr非空,长度判断省略
int mid, L = 0;
int R = arr.length - 1;
int index = -1;
while (L <= R) {
//计算mid, 这样写比(L+R)/2好,因为L+R时会数据溢出
mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于