二分查找学习笔记

前言

二分查找也称折半查找,它是一种效率较高的查找方法。二分查找,思路很简单,细节是魔鬼。

本文主要探究几个最常用的二分查找场景:寻找一个数、寻找左侧、右侧边界。到底要给 mid 加一还是减一,while 里到底用 <= 还是 <,并给出二分模板。

寻找一个数

寻找一个数的问题是最简单最熟悉的,下面的代码相信你也很熟悉:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1; // 注意
while (left <= right) { // 注意
int mid = left + (right - left) / 2;
if (nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}

计算 mid 时需要防止溢出,代码中 left + (right - left) / 2(left + right) / 2 的结果相同,但是有效防止了 leftright 太大直接相加导致溢出。

1. while 中为什么是 <=,而不是 < ?

因为二分的区间为左闭右闭的 [left, right],初始化 right 的赋值是 nums.length - 1

当我们找到了 target 时,即停止搜索

1
2
if(nums[mid] == target)
return mid;

但是如果没找到,搜索区间为空的时候应该终止。

while(left <= right) 的终止条件是 left > right,这个时候搜索区间为空,搜索应终止,举例来说,left = 3right = 2,这个时候搜索区间为 [3, 2],应退出循环返回 -1

while(left < right) 的终止条件是 left >= right,同样举例来说,left = 2right = 2,按照前面的条件这时候应该终止,但是搜索区间为 [2, 2],仍然还有元素未被搜索,说明这是错误的。

如果一定要用 while(left < right) 需要额外添加条件:

1
2
3
4
5
//...
while(left < right) {
// ...
}
return nums[left] == target ? left : -1;

2. 为什么更新 left 和 right 时,有些有写 ± 1,有些没有?

不同问题的处理方法不同,这也是容易混淆的点。

对于寻找一个数的问题来说,如果 nums[mid] != target,那么我们就需要去寻找 [left, mid - 1] 或者 [mid + 1, right],因为 mid 已经查找过了,不需要再次查找。

寻找左(右)侧边界

接下来进一步探讨,寻找左(右)侧边界。

由于左右侧边界的二分查找写法非常多,有的 right = nums.length,有的right = nums.length - 1;有的 left < right,有的 left <= right;有的 return 减 1,有的不减。

下面直接介绍我自己认为比较好用的,好理解的二分模板,仅供参考。

二分模板一共有两个,分别适用于不同情况。

  1. 找大于等于给定数的第一个位置 (满足某个条件的第一个数)
  2. 找小于等于给定数的最后一个数 (满足某个条件的最后一个数)

  • 如果要找左侧边界,即红色端点,用模板 1

  • 如果要找右侧边界,即绿色端点,用模板 2

二分查找模板的几个要点

  1. 循环条件是 l < r
  2. if 的判断条件是让 mid 落在满足你想要结果的区间内
  3. 如果更新操作是 r = mid - 1 或者 l = mid,此时为了防止死循环,计算 mid 时需要加 1。
  4. 出循环一定是 l == r

模板 1

当我们将区间 [l, r] 划分成 [l, mid][mid + 1, r] 时,其更新操作是 r = mid 或者 l = mid + 1,计算 mid 时不需要加 1

1
2
3
4
5
6
7
8
9
10
int bsearch_1(int l, int r) {
while (l < r) {
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
return l;
}

对 check 的说明:

判断条件很复杂时用 check 函数,否则 if 后直接写条件即可

例如:nums[mid] >= target

能二分的题一定是满足某种性质,分成左右两部分

模板 2

当我们将区间 [l, r] 划分成 [l, mid - 1][mid, r] 时,其更新操作是 r = mid - 1 或者 l = mid,此时为了防止死循环,计算 mid 时需要加 1

1
2
3
4
5
6
7
8
9
10
int bsearch_2(int l, int r) {
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
return l;
}

关于 mid = l + r + 1 >> 1 为什么要加 1 的问题,

l == r - 1 时,mid 会等于 l,那么此时如果执行 l = mid 就死循环了。

浮点数二分

1
2
3
4
5
6
7
8
9
10
11
double bsearch_3(double l, double r) {
const double eps = 1e-6; // eps 表示精度,取决于题目对精度的要求
while (r - l > eps) {
double mid = (l + r) / 2;
if (check(mid))
r = mid;
else
l = mid;
}
return l;
}

例题

参考