二分查找
前言
虽然二分就那么简单的几行代码,但是我之前一直搞不懂里面的一些判断是不是要加等于号,更新边界要不要加1或者减1。
每次写的时候就玄学写,可能成功,也可能死循环。但是,其实只要明确了「搜索区间」和「收缩逻辑」,执行逻辑不漏掉元素,就很好办了。
初学编写代码时,我们习惯条件判断中的将最后一个分支经常被else
代替,或者如果两个分支条件的执行逻辑相同时将两个分支合二为一,我觉得这样对思考二分流程是不利的。
另外,整数溢出的问题已经是老生常谈了,少用(l + r) / 2
,改用l + (r - l) >> 1
。
查找元素
常用模板如下:
1 | public int search(int[] nums, int target) { |
这里我习惯使用闭区间进行搜索,这样收缩区间时候的+1
和-1
逻辑也是对称的,很好记忆。
(1)搜索区间
这里搜索闭区间[l, r]
,终止条件为l = r + 1
,因为这时候[r + 1, r]
为空区间。
如果将终止条件改为l = r
,那么终止时候闭区间为[r, r]
,它还包含一个数nums[r]
,在返回时候判断一下nums[r]
与target
的大小即可。
(2)收缩逻辑
- 如果
nums[m] < target
,说明[l, m]
整个区间都小于target
,因此接下来向右收缩,搜索[m + 1, r]
即可,于是我们把l
更新为m + 1
。 - 如果
nums[m] > target
,说明[m, r]
整个区间都大于target
,因此接下来向左收缩,搜索[l, m - 1]
即可,于是我们把r
更新为m - 1
。
查找左边界
常用模板如下:
1 | public int searchLeft(int[] nums, int target) { |
(1)搜索区间
这里搜索区间[l, r)
,终止条件为l = r
,因为这时候区间[r, r)
是一个空区间。
(2)收缩逻辑
- 如果
nums[m] = target
,这时候刚好找到了target
,不要立即返回,而是缩小区间的右边界,将r
更新为m
,在区间[l, m)
中继续搜索,不断向左收缩,达到锁定左侧边界的目的。 - 如果
nums[m] < target
,说明[l, m]
整个区间都小于target
,因此接下来向右收缩,搜索[m + 1, r]
即可,于是我们把l
更新为m + 1
。 - 如果
nums[m] > target
,说明[m, r]
整个区间都大于target
,因此接下来向左收缩,搜索[l, m]
即可,于是我们把r
更新为m
。
(3)越界情况
如果目标数字比数组最后一个数字还要大,那么循环结束后l = nums.length
,因此需要做一个越界判断。
比如在[2, 2]中查找3,那么步骤如下:
步骤 | 执行前(l, r) | m | 执行后(l, r) |
---|---|---|---|
1 | (0, 2) | 1 | (2, 2) |
循环结束,l = r = 2,已经越界,所以需要判断。
(4)双闭写法
1 | public int searchLeft(int[] nums, int target) { |
查找右边界
常用模板如下:
1 | public int searchRight(int[] nums, int target) { |
(1)搜索区间
在循环中搜索左闭右开区间[l, r)
,终止条件l = r
。
但是,注意if (nums[m] == target) l = m + 1
这个语句,一旦nums[m]
与target
相等,l
就等于m+1
,所以循环结束之后,nums[l]
必然不等于target
,最终l
比右边界大1,返回的时候需要把l-1
。
(2)收缩逻辑
- 如果
nums[m] = target
,这时候刚好找到了target
,不要立即返回,而是缩小区间的左边界,将l
更新为m + 1
,在区间[m + 1, r)
中继续搜索,不断向右收缩,达到锁定右侧边界的目的。 - 如果
nums[m] < target
,说明[l, m]
整个区间都小于target
,因此接下来向右收缩,搜索[m + 1, r]
即可,于是我们把l
更新为m + 1
。 - 如果
nums[m] > target
,说明[m, r]
整个区间都大于target
,因此接下来向左收缩,搜索[l, m]
即可,于是我们把r
更新为m
。
(3)越界情况
如果目标数字比数组第一个数字还要大,那么循环结束后l = 0
,因此需要做一个越界判断。
比如在[2, 2]中查找1,那么步骤如下:
步骤 | 执行前(l, r) | m | 执行后(l, r) |
---|---|---|---|
1 | (0, 2) | 1 | (0, 1) |
2 | (0, 1) | 0 | (0, 0) |
循环结束,l = r = 0,(l - 1)已经越界,所以需要判断。
力扣练习
题型1:二分下标(在数组中查找符合条件的元素的下标)
一般而言这个数组是有序的,也可能是半有序的(旋转有序数组或者山脉数组)。
题型2:二分答案(在一个有范围的区间里搜索一个整数)
定位一个有范围的整数,这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数,这个整数有明确的范围,可以考虑使用二分查找。
题目 |
---|
69. 平方根(简单) |
287. 寻找重复数(中等) |
374. 猜数字大小(简单) |
1300. 转变数组后最接近目标值的数组和 |
题型3:二分答案的升级版(判别条件需要遍历数组)
题目 |
---|
410. 分割数组的最大值(困难) |
875. 爱吃香蕉的珂珂(中等) |
LCP 12. 小张刷题计划(中等) |
1482. 制作 m 束花所需的最少天数(中等) |
1552. 两球之间的磁力(中等) |
参考资料
[1] 💤 labuladong力扣T704题解
[2] 💫 liweiwei哥哥力扣T35题解