二分查找统一框架
二分查找同一框架
一般遇到数组单调或者值域(需要求的问题答案)单调,这时候就可以想到是不是考察二分查找。二分查找场景一般分为3种场景:
- 寻找一个数:
例:[1,2,3,4,5,6],要找2的索引1就是这种情形 - 寻找左侧边界:
例:[1,1,2,2,2,6],要找2左边界的索引2就是这种情形 - 寻找右侧边界:
例:[1,1,2,2,2,6],要找2右边界的索引4就是这种情形
二分查找框架
以下是二分查找的一般框架,...部分,是需要根据不同情况,处理的细节问题。
1 | int binarySearch(int[]nums, int target) { |
场景1:寻找一个数
这个场景是最简单的,肯能也是⼤家最熟悉的,即搜索⼀个数,如果存在, 返回其索引,否则返回 -1。
先说缺陷:
1 | int binarySearch(int[]nums, int target) { |
- 为什么
while(left<=right),不是while(left<right)?
核心原因:因为right定义不同:
- right = nums.length - 1时,遍历区间是[left,right],while循环终止条件是left > right,left=right时
(例:[2,2]),还有2这个元素没进循环(简单的数学集合问题); - right = nums.length时,遍历区间是[left,right),while循环终止条件是left >= right,left=right时
(例:[2,2)),区间为空不需要进循环了(还是简单的数学集合问题)。
left <= right 配合 right = nums.length - 1 → **闭区间 [left, right]**,搜索范围是合法下标。
right = nums.length 配合 left < right → **左闭右开区间 [left, right)**,这是另一套二分模板。
left <= right:区间里还有元素可以搜 比如 left=2,right=2:里面还有一个元素,必须进循环判断- 找到 nums [mid] < target:目标在右边,mid 已经排除,
left = mid + 1 - nums [mid] > target:目标在左边,mid 排除,
right = mid - 1
例子:left=right=2,进入循环,判断完,要么 return,要么 left=3 或者 right=1,循环结束。
❌ 如果闭区间写成 left < right:当 left==right 时直接退出,漏掉这个元素!
- 改成
right = nums.length→ 区间变成 [left, right) 左闭右开
此时:
- 下标范围:0 ~ nums.length-1;right = len 是越界的、不包含的边界
- 区间为空的条件:
left >= right,循环条件要改成left < right - 边界赋值也要变:
- nums [mid] < target:目标在右边,mid 可以丢掉,
left = mid + 1 - nums[mid] > target:目标在左边,mid有可能是答案,不能直接 mid-1,
right = mid,因为right区间是开区间。
- nums [mid] < target:目标在右边,mid 可以丢掉,
✅ 左闭右开完整模板:
1 | int binarySearch(int[]nums, int target) { |
总结:
| 模式 | 初始 right | 循环条件 | mid 偏大 (nums [mid]>target) | 区间 |
|---|---|---|---|---|
| 闭区间 | nums.length-1 | left <= right | right = mid -1 | [l, r] |
| 左闭右开 | nums.length | left < right | right = mid | [l, r) |
场景2:寻找左侧边界
鉴于场景1有缺陷,寻找左边界这个场景就是使用,左闭右开的二分查找模板。
1 | int left_bound(int[]nums, int target) { |
核心一句话: 这个是左边界二分(找第一个 ≥ target 的位置),循环退出条件是
left == right,此时 left 和 right 是同一个值,返回 left 和返回 right 完全一样。
- 循环什么时候停下来?
区间是左闭右开 [left, right) 循环条件:while(left < right) 只要 left < right 就继续收缩区间; 当 left == right → [x, x),空区间,循环停止。 👉 退出时 left == right,两者等价,return left /return right 都可以。
- 为什么
nums[mid]==target时写right=mid?
目标:不要停下,继续往左边搜,看前面还有没有相同的 target 例子:nums = [1,2,2,2,3],target=2
- 找到 mid 位置是 2,不直接 return;
- 把右边界压到 mid,新区间变成
[left, mid),继续在左边区间找; - 不断压缩,直到区间收敛到最左边那个 2 的下标。
这就是「左边界」:第一个等于 target 的位置。
- 举一遍例子:nums=[1,2,2,2,3], target=2
初始:left=0, right=5 → [0,5)
mid=2,nums[2]=2 == target → right=2 → [0,2)
mid=1,nums[1]=2 == target → right=1 → [0,1)
mid=0,nums [0]=1 < target → left=1 → left==right=1,退出 return left=1,正好是第一个 2 的下标。
target 不存在的时候,返回值是什么?
返回的是第一个大于 target 的下标(插入位置) nums=[1,3,5], target=2 收敛之后 left=1,代表 2 应该插在下标 1 的位置,数组保持有序。
⚠️ 重要:这个函数没有判断返回值是否越界、nums [left] 是不是等于 target! 所以它返回的 left 有两种情况:
- 找到 target:left = 第一个 target 下标
- 找不到 target:left = 插入位置(0~nums.length) 如果你想像普通二分一样找不到返回 - 1,循环结束后要加判断:
1 | if (left == nums.length || nums[left] != target) { |
- 为什么没有返回 -1 的操作?如果nums 中不存在target 这个值,怎么办?
对于nums=[1,2,2,2,3]这个数组,以上算法返回1。这个1的含义:nums中小于2的元素有1个。
⽐如对于有序数组 nums = [2,3,5,7] , target = 1 ,算法会返回 0,含义是: nums 中⼩于 1 的元素有 0 个。
再⽐如说 nums = [2,3,5,7], target = 8 ,算法会返回 4,含义是: nums 中⼩于 8 的元素有 4 个。
综上可以看出,函数的返回值(即 left 变量的值)取值区间是闭区间 [0, nums.length] ,所以我们简单添加两⾏代码就能在正确的时候 return -1。
1 | while (left < right) { //... |
场景3:寻找右侧边界
类似寻找左侧边界的算法,这⾥也会提供两种写法,还是先写常⻅的左闭右 开的写法,只有两处和搜索左侧边界不同,已标注:
1 | int right_bound(int[]nums, int target) { |
为什么最后返回 left - 1 ⽽不像左侧边界的函数,返回 我觉得这⾥既然是搜索右侧边界,应该返回 right 才对。
⾸先,while 循环的终⽌条件是 left == right ,所以 left 和 是⼀样的,你⾮要体现右侧的特点,返回 right - 1 好了。⾄于为什么要减⼀,这是搜索右侧边界的⼀个特殊点,关键在这个条件判 断:
1
2
3if (nums[mid] == target) {
left = mid + 1;
// 这样想: mid = left - 1为什么没有返回 -1 的操作?如果nums 中不存在target 这个值,怎么办?
类似之前的左侧边界搜索,因为 while 的终⽌条件是 left == right , 就是说 left 的取值范围是 [0, nums.length] ,所以可以添加两⾏代码,正确地返回 -1:
1 | while (left < right) { |
总结
开闭区间不好记忆,可以将3个场景都统一成闭区间,方便记忆。只要明⽩了「搜索区间」这个概念,就能有效避免漏掉元 素,随便你怎么改都⾏。
这是【闭区间版本
[left, right]的左边界二分】1
2
3
4
5
6
7
8
9
10
11
12
13
14
15while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// mid 太小,target 在 mid 右边,mid 可以扔掉
left = mid + 1;
} else if (nums[mid] > target) {
// mid 太大,target 在 mid 左边,mid 扔掉
right = mid - 1;
} else if (nums[mid] == target) {
// ✅ 重点:找到了 target,但不停止!向左压缩,找更靠左的相同值
right = mid - 1;
}
if (left >= nums.length || nums[left] != target) return -1;
return left;
}区间定义:
[left, right],左右都包含,循环条件left <= right
拆开讲每一支
nums[mid] < targetmid 的值比目标小 → target 一定在 mid 的右边 mid 已经看过、没用了,新区间:[mid+1, right]``left = mid + 1nums[mid] > targetmid 的值比目标大 → target 一定在 mid 的左边 mid 看过、没用,新区间:[left, mid-1]``right = mid - 1nums[mid] == targetmid 已经等于 target,但是我们要【左边界】(第一个 target) 现在只知道 mid 是 target,但它左边可能还有一样的 target! 所以:继续往左边搜 把右边界压到 mid-1,新区间变成[left, mid - 1]
👉 不是直接 return,而是把右边界往左收,继续循环在左边找更早出现的 target
⚠️ 和左闭右开那套左边界写法对比:
- 左闭右开找到 target:
right = mid - 闭区间找到 target:
right = mid - 1因为区间含义不一样!闭区间里 mid 已经确认是 target,不能留在候选区间里了。
这是【闭区间版本
[left, right]的右边界二分】
1 | int right_bound(int[]nums, int target) { |
- 为什么右边界最后返回
right?
目标:找最后一个等于 target 的位置 当 nums[mid]==target,我们执行 left = mid + 1 含义:
当前 mid 是 target,但我要去右边看看还有没有 target,所以把搜索区间改成
[mid+1, right]
相当于:left 主动往 target 的右边冲,一直冲到越过最后一个 target。 一旦 left 冲过头,left = right + 1,循环停下:
left:落在「最后一个 target 的下一位」right:被留在「最后一个 target 的位置」
例子:nums=[1,2,2,2,3],target=2 循环结束:left=4,right=3 right=3 就是最后一个 2,left=4 是它后面。 👉 所以返回 right。
对比一下:
- 闭区间左边界:找到 target 时
right = mid -1,right 往左边冲过头,答案留在 left - 闭区间右边界:找到 target 时
left = mid +1,left 往右边冲过头,答案留在 right
- 为什么校验要写
right < 0?
什么时候 right < 0? target 比数组里所有元素都小,所有元素都 > target 举例子:nums=[2,4,6],target=1 初始:left=0, right=2
- mid=1,nums[1]=4 > 1 → right=0
- mid=0,nums [0]=2 > 1 → right=-1 现在
left=0,right=-1,满足left>right,循环退出。 right = -1,不是合法下标,直接返回 -1。
为什么左边界不会判断
left<0? 左边界是 left 向右走,left 最小只能是 0,不可能变成负数; 右边界是 right 向左一直减,可以减到 -1,所以必须判断right < 0。