二分查找统一框架

二分查找同一框架


一般遇到数组单调或者值域(需要求的问题答案)单调,这时候就可以想到是不是考察二分查找。二分查找场景一般分为3种场景:

  1. 寻找一个数:例:[1,2,3,4,5,6],要找2的索引1就是这种情形
  2. 寻找左侧边界:例:[1,1,2,2,2,6],要找2左边界的索引2就是这种情形
  3. 寻找右侧边界:例:[1,1,2,2,2,6],要找2右边界的索引4就是这种情形

二分查找框架

以下是二分查找的一般框架,...部分,是需要根据不同情况,处理的细节问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[]nums, int target) {
int left = 0, right = ...;
while (...) {
//mid需要防⽌溢出,代码中 `left + (right - left) / 2` 和 `(left + right) / 2`的结果相同,但是有效防⽌了 `left + right` 太⼤直接导致溢出。
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}

场景1:寻找一个数

这个场景是最简单的,肯能也是⼤家最熟悉的,即搜索⼀个数,如果存在, 返回其索引,否则返回 -1。

先说缺陷:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[]nums, int target) {
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;
}
  1. 为什么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 时直接退出,漏掉这个元素!

  1. 改成 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区间是开区间。

✅ 左闭右开完整模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[]nums, int target) {
int left = 0;
int right = nums.length; // [left, right)
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; // 重点!不是mid-1
}
return -1;
}

总结:

模式 初始 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int left_bound(int[]nums, int target) {
if (nums.length == 0)
return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意 }
}
}
return left;
}

核心一句话: 这个是左边界二分(找第一个 ≥ target 的位置),循环退出条件是 left == right,此时 left 和 right 是同一个值,返回 left 和返回 right 完全一样。


  1. 循环什么时候停下来?

区间是左闭右开 [left, right) 循环条件:while(left < right) 只要 left < right 就继续收缩区间; 当 left == right → [x, x),空区间,循环停止。 👉 退出时 left == right,两者等价,return left /return right 都可以。

  1. 为什么 nums[mid]==target 时写 right=mid?

目标:不要停下,继续往左边搜,看前面还有没有相同的 target 例子:nums = [1,2,2,2,3],target=2

  • 找到 mid 位置是 2,不直接 return;
  • 把右边界压到 mid,新区间变成 [left, mid),继续在左边区间找;
  • 不断压缩,直到区间收敛到最左边那个 2 的下标。

这就是「左边界」:第一个等于 target 的位置。

  1. 举一遍例子:nums=[1,2,2,2,3], target=2

初始:left=0, right=5 → [0,5)

  1. mid=2,nums[2]=2 == target → right=2 → [0,2)

  2. mid=1,nums[1]=2 == target → right=1 → [0,1)

  3. mid=0,nums [0]=1 < target → left=1 → left==right=1,退出 return left=1,正好是第一个 2 的下标。

  4. target 不存在的时候,返回值是什么?

返回的是第一个大于 target 的下标(插入位置) nums=[1,3,5], target=2 收敛之后 left=1,代表 2 应该插在下标 1 的位置,数组保持有序。

⚠️ 重要:这个函数没有判断返回值是否越界、nums [left] 是不是等于 target! 所以它返回的 left 有两种情况:

  1. 找到 target:left = 第一个 target 下标
  2. 找不到 target:left = 插入位置(0~nums.length) 如果你想像普通二分一样找不到返回 - 1,循环结束后要加判断:
1
2
3
4
if (left == nums.length || nums[left] != target) {
return -1;
}
return left;
  1. 为什么没有返回 -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
2
3
4
5
6
7
8
9
10
11
while (left < right) { //...

}
// target ⽐所有数都⼤
if (left == nums.length) return -1;
// 能走到这里,说明 left 是**合法下标(0 ≤ left < nums.length)。然后判断:如果nums[left] == target:
//找到了,这个 left 就是第一个等于 target 的位置(左边界),返回 left
//如果不等:说明 target 应该插在 left 这个位置,但是数组里本来就没有 target → 返回 -1
//例子:nums=[1,3,5],target=2
//收敛后 left=1,nums[1]=3≠2,所以返回 -1。类似之前算法的处理⽅式
return nums[left] == target ? left : -1;

场景3:寻找右侧边界

类似寻找左侧边界的算法,这⾥也会提供两种写法,还是先写常⻅的左闭右 开的写法,只有两处和搜索左侧边界不同,已标注:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int right_bound(int[]nums, int target) {
if (nums.length == 0)
return -1;
int left = 0,
right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
  1. 为什么最后返回 left - 1 ⽽不像左侧边界的函数,返回 我觉得这⾥既然是搜索右侧边界,应该返回 right 才对。

    ⾸先,while 循环的终⽌条件是 left == right ,所以 left 和 是⼀样的,你⾮要体现右侧的特点,返回 right - 1 好了。⾄于为什么要减⼀,这是搜索右侧边界的⼀个特殊点,关键在这个条件判 断:

    1
    2
    3
    if (nums[mid] == target) {
    left = mid + 1;
    // 这样想: mid = left - 1
  2. 为什么没有返回 -1 的操作?如果nums 中不存在target 这个值,怎么办?

    类似之前的左侧边界搜索,因为 while 的终⽌条件是 left == right , 就是说 left 的取值范围是 [0, nums.length] ,所以可以添加两⾏代码,正确地返回 -1:

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

总结

开闭区间不好记忆,可以将3个场景都统一成闭区间,方便记忆。只要明⽩了「搜索区间」这个概念,就能有效避免漏掉元 素,随便你怎么改都⾏。

  1. 这是【闭区间版本 [left, right] 的左边界二分】

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    while (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


    拆开讲每一支

    1. nums[mid] < target mid 的值比目标小 → target 一定在 mid 的右边 mid 已经看过、没用了,新区间:[mid+1, right]``left = mid + 1
    2. nums[mid] > target mid 的值比目标大 → target 一定在 mid 的左边 mid 看过、没用,新区间:[left, mid-1]``right = mid - 1
    3. nums[mid] == targetmid 已经等于 target,但是我们要【左边界】(第一个 target) 现在只知道 mid 是 target,但它左边可能还有一样的 target! 所以:继续往左边搜 把右边界压到 mid-1,新区间变成 [left, mid - 1]

    👉 不是直接 return,而是把右边界往左收,继续循环在左边找更早出现的 target

    ⚠️ 和左闭右开那套左边界写法对比:

    • 左闭右开找到 target:right = mid
    • 闭区间找到 target:right = mid - 1 因为区间含义不一样!闭区间里 mid 已经确认是 target,不能留在候选区间里了。
  2. 这是【闭区间版本 [left, right] 的右边界二分】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int right_bound(int[]nums, int target) {
int left = 0,
right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// mid 是 target,但右边可能还有,把左边界往右推,继续搜右侧
left = mid + 1;
}
}
// 这⾥改为检查 right 越界的情况,⻅下图
// 校验:right越界 或者 这个位置不是target → 返回-1
if (right < 0 || nums[right] != target) return -1;
return right;
}
  1. 为什么右边界最后返回 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
  1. 为什么校验要写 right < 0?

什么时候 right < 0? target 比数组里所有元素都小,所有元素都 > target 举例子:nums=[2,4,6],target=1 初始:left=0, right=2

  1. mid=1,nums[1]=4 > 1 → right=0
  2. 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。

------------- 本 文 结 束     感 谢 您 的 阅 读 -------------