二分查找算法是一种在有序数组中查找特定元素的常用算法，它的时间复杂度为 O(log n)；由于每次查找都将数组规模减半，因此算法的效率非常高。本文记录了二分查找的常见场景，给出在升序数组中：
- 查找给定目标值的索引；
- 查找大于等于目标值的最小索引、查找大于目标值的最小索引；
- 查找小于等于目标值的最大索引、查找小于目标值的最大索引。
二分查找难点
二分查找最难把握的就是：
while 循环的条件到底要不要加等于号：- 不同的
if 判断下，要不要加、减一。
记住，在 while 条件不加「等号」时，l 和 r 只有一个加（或减）一；在 while 条件加「等号」时，l 和 r 都有加一（或减）一。然后，再梳理清楚其它细节即可。
查找目标值的索引
例如，升序数组为 [1, 3, 5, 7, 12, 12, 12, 13, 16]，目标值为 12，那么可能返回索引 4, 5, 6 中的一个。若目标值不存在，则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int binarySearch(int arr[], int target, int l, int r) {
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] < target) {
l = mid + 1;
} else if (arr[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return -1;
}
|
查找大于等于目标值的最小索引（下限）
例如，升序数组为 [1, 3, 5, 7, 12, 12, 12, 13, 16]，目标值为 12，那么应该返回索引 4。若数组中不存在大于等于目标值的数，则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
|
int findGreateEq(int arr[], int target, int l, int r) {
while (l < r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
return arr[l] >= target ? l : -1;
}
|
因为查找的是「大于等于 目标值的最小索引」，所以在 mid 位置：
- 小于目标值时，最小索引应该落在区间
[mid + 1, r]，所以 l 更新为 l = mid + 1。
- 大于等于 目标值时，最小索引应该落在区间
[l, mid]，所以 r 更新为 r = mid，而不是 r = mid - 1；
查找大于目标值的最小索引
例如，升序数组为 [1, 3, 5, 7, 12, 12, 12, 13, 16]，目标值为 12，那么应该返回索引 7。若数组中不存在大于目标值的数，则返回 -1。
1
2
3
4
5
6
7
8
9
10
11
12
|
int findGreate(int arr[], int target, int l, int r) {
while (l < r) {
int mid = l + ((r - l) >> 1);
if (arr[mid] <= target) {
l = mid + 1;
} else {
r = mid;
}
}
return arr[l] > target ? l : -1;
}
|
因为查找的是「大于 目标值的最小索引」，所以在 mid 位置：
- 小于等于目标值时，最小索引应该落在区间
[mid + 1, r]，所以 l 更新为 l = mid + 1。
- 大于 目标值时，最小索引应该落在区间
[l, mid]，所以 r 更新为 r = mid，而不是 r = mid - 1；
查找小于等于目标值的最大索引（上限）
例如，升序数组为 [1, 3, 5, 7, 12, 12, 12, 13, 16]，目标值为 12，那么应该返回索引 6。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int findLessEq(int arr[], int target, int l, int r) {
while (l < r) {
int mid = l + ((r + 1 - l) >> 1);
if (arr[mid] <= target) {
l = mid;
} else {
r = mid - 1;
}
}
return arr[r] <= target ? r : -1;
}
|
因为查找的是「小于等于 目标值的最大索引」，所以在 mid 位置：
- 小于等于 目标值时，最大索引应该落在区间
[mid, r]，所以 l 更新为 l = mid，而不是 l = mid + 1；
- 大于目标值时，最大索引应该落在区间
[l, mid - 1]，所以 r 更新为 r = mid - 1。
查找小于目标值的最大索引
例如，升序数组为 [1, 3, 5, 7, 12, 12, 12, 13, 16]，目标值为 12，那么应该返回索引 3。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int findLess(int arr[], int target, int l, int r) {
while (l < r) {
int mid = l + ((r + 1 - l) >> 1);
if (arr[mid] < target) {
l = mid;
} else {
r = mid - 1;
}
}
return arr[r] < target ? r : -1;
}
|
因为查找的是「小于 目标值的最大索引」，所以在 mid 位置：
- 小于 目标值时，最大索引应该落在区间
[mid, r]，所以 l 更新为 l = mid，而不是 l = mid + 1；
- 大于等于目标值时，最大索引应该落在区间
[l, mid - 1]，所以 r 更新为 r = mid - 1。
功能测试
测试代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <stdio.h>
int main() {
int arr1[] = {1, 3, 5, 7, 12, 12, 12, 13, 16};
int arr2[] = {0, 1, 3, 5, 7, 11, 12, 13, 16, 17};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
int size2 = sizeof(arr2) / sizeof(arr2[0]);
printf("t\tidx\tgeqIdx\tgIdx\tleqIdx\tlIdx\n");
for (int i = 0; i < size2; i++) {
int target = arr2[i];
int targetIdx = binarySearch(arr1, target, 0, size1 - 1);
int greateEqIdx = findGreateEq(arr1, target, 0, size1 - 1);
int greateIdx = findGreate(arr1, target, 0, size1 - 1);
int lessEqIdx = findLessEq(arr1, target, 0, size1 - 1);
int lessIdx = findLess(arr1, target, 0, size1 - 1);
printf("%d\t%d\t%d\t%d\t%d\t%d\n", target, targetIdx, greateEqIdx, greateIdx, lessEqIdx, lessIdx);
}
return 0;
}
|
测试结果
上述测试代码的测试结果如下，可以发现结果是正确的。
1
2
3
4
5
6
7
8
9
10
11
| t idx geqIdx gIdx leqIdx lIdx
0 -1 0 0 -1 -1
1 0 0 1 0 -1
3 1 1 2 1 0
5 2 2 3 2 1
7 3 3 4 3 2
11 -1 4 4 3 3
12 4 4 7 6 3
13 7 7 8 7 6
16 8 8 -1 8 7
17 -1 -1 -1 8 8
|
