二分查找有几种写法？它们的区别是什么？

二分查找是一种高效的查找算法，其核心思想是利用有序数组的特性，不断将搜索范围缩小一半，直到找到目标元素或确定目标元素不存在。二分查找的写法主要有以下几种，它们的区别在于处理边界条件和循环退出条件的方式不同。

下面我们将详细介绍这几种写法，并分析它们的区别：

基本思路（通用）：

1. 前提条件： 待查找的数组必须是有序的（通常是升序或降序）。
2. 定义搜索范围： 使用两个指针，通常是 `left` (或 `low`) 和 `right` (或 `high`)，分别指向当前搜索范围的起始索引和结束索引。
3. 计算中间索引： 在每次迭代中，计算中间索引 `mid`。
4. 比较： 将目标值 `target` 与 `nums[mid]` 进行比较。
如果 `target == nums[mid]`，则找到目标元素，返回 `mid`。
如果 `target < nums[mid]`，则目标元素（如果存在）一定在 `mid` 的左侧，将搜索范围缩小到左半部分，更新 `right = mid 1`。
如果 `target > nums[mid]`，则目标元素（如果存在）一定在 `mid` 的右侧，将搜索范围缩小到右半部分，更新 `left = mid + 1`。
5. 循环继续： 重复步骤 3 和 4，直到搜索范围为空 (`left > right`)。
6. 未找到： 如果循环结束时仍未找到目标元素，则说明目标元素不存在于数组中，通常返回一个特殊值（如 1）。

常见的几种写法：

我们主要从循环的条件和 `mid` 的计算方式来区分不同的写法。



写法一：传统循环条件 `left <= right`

这是最常见和直观的二分查找写法。

核心特点：

循环条件： `while (left <= right)`。这意味着当 `left` 等于 `right` 时，循环仍然会执行一次。
更新 `right`： 当 `target < nums[mid]` 时，更新 `right = mid 1`。这是为了排除当前 `mid` 元素，因为我们已经知道 `target` 小于 `nums[mid]`。
更新 `left`： 当 `target > nums[mid]` 时，更新 `left = mid + 1`。同样，排除当前 `mid` 元素。
`mid` 的计算： `mid = left + (right left) / 2`。这种计算方式可以避免 `left + right` 溢出的风险（虽然在大多数现代语言中整数溢出不是大问题，但这是个好的编程习惯）。

示例代码 (Python):

```python
def binary_search_v1(nums, target):
left, right = 0, len(nums) 1
while left <= right:
mid = left + (right left) // 2 避免溢出
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else: nums[mid] > target
right = mid 1
return 1 target not found

例子
arr = [2, 5, 7, 8, 11, 12]
print(f"v1: Index of 13: {binary_search_v1(arr, 13)}") Output: v1: Index of 13: 1
print(f"v1: Index of 12: {binary_search_v1(arr, 12)}") Output: v1: Index of 12: 5
print(f"v1: Index of 2: {binary_search_v1(arr, 2)}") Output: v1: Index of 2: 0
print(f"v1: Index of 8: {binary_search_v1(arr, 8)}") Output: v1: Index of 8: 3
```

详细解析：

当 `left == right` 时，`mid` 会等于 `left` (或者 `right`)。
如果 `nums[mid] == target`，则正确返回 `mid`。
如果 `nums[mid] < target`，则 `left` 会更新为 `mid + 1`。此时 `left` 会大于 `right` (`left` 变成了 `right + 1`)，循环结束。
如果 `nums[mid] > target`，则 `right` 会更新为 `mid 1`。此时 `right` 会小于 `left` (`right` 变成了 `left 1`)，循环结束。

这种写法保证了在每次迭代后，如果目标值不在 `mid` 位置，则搜索范围 `[left, right]` 会被正确地缩小，并且最终当 `left > right` 时，搜索范围会完全排除。

优点：
逻辑清晰，易于理解。
覆盖了所有可能的情况，包括单元素数组。

缺点：
在某些特定问题中（例如查找第一个大于某个值的元素），可能需要微调。



写法二：循环条件 `left < right`，查找 第一个等于 目标值的元素 (变种)

这种写法在循环条件上有所不同，并且在更新指针时会略有区别，通常用于查找满足某种条件的第一个或最后一个元素。为了演示差异，我们来看一个稍微修改过的版本，目的是查找第一个等于 `target` 的元素。

核心特点：

循环条件： `while (left < right)`。当 `left` 等于 `right` 时，循环停止。
更新 `right`： 当 `nums[mid] < target` 时，更新 `left = mid + 1`。
更新 `right` (关键差异)： 当 `nums[mid] >= target` 时，更新 `right = mid`。 注意这里是 `right = mid`，而不是 `mid 1`。 这是因为 `mid` 可能是我们要找的目标值（第一个等于 target 的元素），所以不能直接排除它。我们只是将搜索范围缩小到 `[left, mid]`。
最终结果： 循环结束后，`left` (或 `right`) 指向的是第一个大于等于 `target` 的元素。如果 `nums[left] == target`，则找到了。

示例代码 (Python) 查找第一个等于 target 的元素:

```python
def binary_search_v2_first_occurrence(nums, target):
left, right = 0, len(nums) 1
优化：如果数组为空或者目标值小于第一个元素或大于最后一个元素，可以直接返回
if not nums or target < nums[0] or target > nums[1]:
return 1

while left < right:
mid = left + (right left) // 2
if nums[mid] < target:
left = mid + 1
else: nums[mid] >= target
right = mid 保留mid作为潜在的答案

循环结束后，left指向第一个大于等于target的元素
if nums[left] == target:
return left
else:
return 1 target not found

例子
arr = [2, 5, 7, 8, 11, 12, 12, 15]
print(f"v2: Index of 12 (first): {binary_search_v2_first_occurrence(arr, 12)}") Output: v2: Index of 12 (first): 5
print(f"v2: Index of 8: {binary_search_v2_first_occurrence(arr, 8)}") Output: v2: Index of 8: 3
print(f"v2: Index of 1: {binary_search_v2_first_occurrence(arr, 1)}") Output: v2: Index of 1: 1
print(f"v2: Index of 13: {binary_search_v2_first_occurrence(arr, 13)}") Output: v2: Index of 13: 1
```

详细解析：

当 `left < right` 时，`mid` 总是严格小于 `right` (因为 `mid = left + (right left) // 2` 且 `left < right`。如果 `left + 1 == right`，`mid = left`。 如果 `left == right`，循环就结束了)。
如果 `nums[mid] >= target`，我们将 `right` 设置为 `mid`。 这意味着搜索范围变成了 `[left, mid]`。
循环的终止条件是 `left == right`。 此时，`left` (或 `right`) 指向的元素，是数组中第一个大于等于 `target` 的元素。
最后需要检查 `nums[left]` 是否真的等于 `target` 来确认是否找到。

什么时候用？
这种写法非常适合需要查找第一个满足某个条件的元素，例如：
查找第一个等于目标值的元素。
查找第一个大于目标值的元素（Upper Bound）。
查找第一个大于等于目标值的元素（Lower Bound）。

优点：
在查找边界值（第一个/最后一个出现）时非常有效。
避免了在处理 `nums[mid] >= target` 时丢失潜在的答案。

缺点：
逻辑相对复杂一些，需要仔细理解 `right = mid` 的含义。
最后需要额外的判断来确认是否真的找到了目标值。



写法三：循环条件 `left < right`，查找 任意一个 等于目标值的元素 (变种)

这种写法与写法一类似，但循环条件是 `left < right`。在处理 `nums[mid] == target` 的情况时，也需要注意。

核心特点：

循环条件： `while (left < right)`。
更新 `right`： 当 `nums[mid] >= target` 时，更新 `right = mid`。
更新 `left`： 当 `nums[mid] < target` 时，更新 `left = mid + 1`。
`mid` 的计算： `mid = left + (right left + 1) // 2`。 注意这里是 `+ 1`。 这种写法是为了防止 `mid` 总是等于 `left` 的情况，从而避免死循环。当 `left = 0`, `right = 1` 时，`mid = 0 + (1 0) // 2 = 0`。如果 `nums[mid] < target`，`left` 会变成 `mid + 1 = 1`。此时 `left == right`，循环结束。

为什么需要 `+ 1` 呢？

考虑 `left = 0, right = 1`。
如果使用 `mid = left + (right left) // 2`，则 `mid = 0 + (1 0) // 2 = 0`。
如果 `nums[0] < target`，那么 `left` 会更新为 `mid + 1 = 1`。 此时 `left` 变成 `1`，`right` 还是 `1`，`left` 就等于 `right` 了，循环就会退出。
但是，如果 `nums[0] >= target`，那么 `right` 会更新为 `mid = 0`。 此时 `left` 是 `0`，`right` 变成 `0`，`left` 就等于 `right` 了，循环也会退出。

这种写法在处理 `left` 和 `right` 相差很小时，如果不调整 `mid` 的计算方式，可能会导致 `mid` 总是取到 `left` 的值，当 `nums[mid] < target` 时，`left` 更新为 `mid + 1`，当 `nums[mid] >= target` 时，`right` 更新为 `mid`。

如果 `mid` 总是等于 `left`，而条件是 `left < right`，当 `left` 和 `right` 相差1时，如果 `nums[mid]` (即 `nums[left]`) 小于 `target`，`left` 会变成 `mid + 1`，此时 `left` 等于 `right`，循环终止。但如果 `nums[mid]` (即 `nums[left]`) 大于等于 `target`，`right` 会变成 `mid`，此时 `right` 就等于 `left` 了，循环也终止。

另一种理解是，`mid = left + (right left + 1) // 2` 相当于 `mid = (left + right + 1) // 2`，这样可以确保 `mid` 向右偏，当 `left` 和 `right` 相差1时，`mid` 会取 `right` 的值。

示例代码 (Python) 查找任意一个等于 target 的元素:

```python
def binary_search_v3_any_occurrence(nums, target):
left, right = 0, len(nums) 1
while left < right:
mid = left + (right left) // 2 standard mid
mid = left + (right left + 1) // 2 mid leans to the right

if nums[mid] == target:
如果要找任意一个，可以先返回，也可以继续缩小范围找第一个/最后一个
这里为了演示，我们先往右边继续找
left = mid
elif nums[mid] < target:
left = mid + 1
else: nums[mid] > target
right = mid 1 此时 nums[mid] > target, mid 肯定不是答案，可以排除

循环结束后 left == right
if nums[left] == target:
return left
else:
return 1

例子
arr = [2, 5, 7, 8, 11, 12]
print(f"v3: Index of 12: {binary_search_v3_any_occurrence(arr, 12)}") Output: v3: Index of 12: 5
print(f"v3: Index of 8: {binary_search_v3_any_occurrence(arr, 8)}") Output: v3: Index of 8: 3
print(f"v3: Index of 1: {binary_search_v3_any_occurrence(arr, 1)}") Output: v3: Index of 1: 1
```

更常见的 `left < right` 写法，查找第一个等于 target 的元素 (等价于 v2 的变种):

上面 v3 的写法是为了演示 `mid` 计算方式的改变，但在实际应用中，`left < right` 的写法更常用于查找第一个/最后一个元素，如 v2 所示。我们再重新回顾一下，以更清晰的方式说明。

示例代码 (Python) 查找第一个等于 target 的元素 (另一种常见写法):

```python
def binary_search_v3_variant(nums, target):
left, right = 0, len(nums) right is exclusive, pointing one past the end
while left < right:
mid = left + (right left) // 2
if nums[mid] < target:
left = mid + 1
else: nums[mid] >= target
right = mid mid could be the answer, so we keep it in the range

After loop, left == right.
If nums[left] == target, then left is the first occurrence.
If left == len(nums) or nums[left] != target, then target is not found.
if left < len(nums) and nums[left] == target:
return left
else:
return 1

例子
arr = [2, 5, 7, 8, 11, 12, 12, 15]
print(f"v3_variant: Index of 12 (first): {binary_search_v3_variant(arr, 12)}") Output: v3_variant: Index of 12 (first): 5
print(f"v3_variant: Index of 8: {binary_search_v3_variant(arr, 8)}") Output: v3_variant: Index of 8: 3
print(f"v3_variant: Index of 1: {binary_search_v3_variant(arr, 1)}") Output: v3_variant: Index of 1: 1
```

详细解析 (v3_variant):

`right` 的初始化： `right = len(nums)`，这是一个半开区间 `[left, right)`。这意味着 `right` 指向的元素不在搜索范围内。
循环条件： `while (left < right)`。 当 `left == right` 时，搜索范围为空，循环结束。
`mid` 的计算： `mid = left + (right left) // 2`。 这个 `mid` 总是落在 `[left, right1]` 范围内。
更新 `right`： 当 `nums[mid] >= target` 时，`right = mid`。 这意味着我们缩小了搜索范围到 `[left, mid)`。`mid` 本身可能就是我们寻找的第一个大于等于 `target` 的元素，所以我们将其包含在新的搜索范围内（右边界 `right` 变为 `mid`）。
更新 `left`： 当 `nums[mid] < target` 时，`left = mid + 1`。 这意味着我们排除了 `mid` 及左边的所有元素。
最终结果： 循环结束后，`left == right`。`left` 指向的是数组中第一个大于等于 `target` 的元素。最后需要检查 `nums[left]` 是否等于 `target` 以及 `left` 是否越界。

这种写法也非常常见，并且在 C++ 的 STL 库的 `lower_bound` 等函数中广泛使用。

优点：
在某些场景下，逻辑更加简洁，特别是当 `right` 指向的是一个半开区间时。
适用于查找第一个大于等于某个值的元素。

缺点：
需要理解半开区间 `[left, right)` 的概念。
对初学者可能稍微难理解一些。



总结与区别比较：

| 特性/写法 | 写法一 (`left <= right`) | 写法二 (`left < right`, `right = mid` for `>=`) | 写法三 (`left < right`, `right = mid` for `>=`) (v3_variant) |
| : | : | : | : |
| 循环条件 | `left <= right` | `left < right` | `left < right` |
| 搜索范围 | `[left, right]` (闭区间) | `[left, right]` (闭区间) | `[left, right)` (半开区间) |
| `mid` 计算 | `left + (right left) // 2` | `left + (right left) // 2` | `left + (right left) // 2` |
| 当 `nums[mid] < target` | `left = mid + 1` | `left = mid + 1` | `left = mid + 1` |
| 当 `nums[mid] >= target`| `right = mid 1` (如果 `target` 还在 `mid` 左边) | `right = mid` (`mid` 可能是答案，保留在范围内) | `right = mid` (`mid` 可能是答案，保留在范围内) |
| 当找到 `target` | 直接返回 `mid` | 继续缩小范围，最终 `left` 指向第一个等于 `target` 的元素 | 继续缩小范围，最终 `left` 指向第一个等于 `target` 的元素 |
| 目标 | 查找任意一个等于 `target` 的元素 | 查找第一个等于 `target` 的元素 | 查找第一个等于 `target` 的元素 |
| 边界处理 | `left == right` 时仍执行一次循环，确保最终 `left > right` 或找到元素。 | 循环终止时 `left == right`，`left` 指向候选结果。 | 循环终止时 `left == right`，`left` 指向候选结果。 |
| 优点 | 逻辑直观，普遍适用。 | 查找边界值（第一个/最后一个）时有效，避免丢失潜在答案。 | 查找边界值有效，与 STL 库风格相似。 |
| 缺点 | 在查找边界值时可能需要额外处理。 | 逻辑稍复杂，最终需额外检查。 | 理解半开区间需要时间，最终需额外检查。 |

如何选择？

1. 查找任意一个匹配项： 写法一 (`left <= right`) 是最直接和通用的方法。
2. 查找第一个匹配项 (或第一个大于/等于的元素)： 写法二 (`left < right` 配合 `right = mid`) 和 写法三 (`left < right` 配合 `right = mid` 且 `right` 为半开区间) 都非常适合。写法的选择可能取决于个人偏好和具体场景，但理解它们背后的逻辑是关键。
3. 查找最后一个匹配项 (或最后一个小于/等于的元素)： 需要微调上述写法，例如在更新 `left` 和 `right` 的逻辑上进行调整。例如，查找最后一个小于等于 `target` 的元素，可以考虑在 `nums[mid] <= target` 时，更新 `left = mid`，而 `nums[mid] > target` 时，更新 `right = mid 1`。

一些额外的注意事项：

整数溢出： `mid = left + (right left) / 2` 是计算中间值的安全方式，可以避免 `left + right` 溢出的情况。
数组为空： 在实现二分查找时，务必考虑空数组的情况。
目标值不存在： 确保在目标值不存在时返回一个明确的信号（如 1）。
重复元素： 如果数组中存在重复元素，那么二分查找找到的可能是任意一个匹配项，而不是第一个或最后一个（除非你专门设计算法去查找）。

理解这几种写法的核心在于：
循环的终止条件是什么？ (`left <= right` vs `left < right`)
搜索范围是如何定义的？ (闭区间 `[left, right]` vs 半开区间 `[left, right)`)
当 `nums[mid]` 与 `target` 比较时，我们如何更新 `left` 和 `right`？ 特别是当 `nums[mid]` 可能就是我们要找的答案时，我们不能直接排除它。

掌握了这些基本原则，你就可以灵活地应用和修改二分查找来解决各种问题了。

更新：一图解释二分法分类

强烈安利C++和Python标准库的超简洁、bug free的通用写法(C++: lower_bound; 感谢评论区指认出Python标准库的bisect_left)

6行Python解决，同时适用于区间为空、答案不存在、有重复元素、搜索开/闭的上/下界等情况：

       def lower_bound(array, first, last, value):  # 求非降序范围[first, last)内第一个不小于value的值的位置     while first < last: # 搜索区间[first, last)不为空         mid = first + (last - first) // 2  # 防溢出         if array[mid] < value: first = mid + 1          else: last = mid     return first  # last也行，因为[first, last)为空的时候它们重合     

的位置调整只出现了一次！而且最后返回first或last都是对的，无需纠结！

诀窍是搜索区间[first, last)左闭右开！

好处都有啥？请下滑看看"Dijkstra的干货/题外话"ヽ(ﾟ▽ﾟ)ノ

（你一直在用的）两头闭区间[l, r]写出来的binary search一般免不了多写一两个+1,-1,return，而且区间为空时l和r只有一个是正确答案，极易出错，除非你有肌肉记忆。

如果你想求的不是第一个不小于value的值的位置，而是任意等于value的值的位置，你可以在更新[first, last)区间之前先检查array[mid] == value是否成立。以下我们只讨论广义的求上界、下界的二分搜索，适用于完全相等的值不存在的情况。

担心搞错范围/终止条件/edge case？

array不是升序怎么办？

且听我徐徐道来ヽ(ﾟ▽ﾟ)ノ

---

二分查找有几种写法？

一图即可解释，在array中搜索value=3：

Binary search找的无非是四个箭头中的一个：开/闭区间，上/下界。C++和Python标准库都只提供了找下界的函数，下标减一即可获得相邻互补的上界。如果只需找任意一个黄色value，可直接找闭区间下界（红箭头），然后再检查一次是否等于value；当然，也可以在二分法循环中检查。只讨论输入array是非降序non-descending order的情况。其他情况，如降序，可以通过自定义比较函数轻松转化为这种情况而无需修改原array。

一、搜索区间和中点

i) 求下界，即找满足x >= value或x > value条件的最小x的位置，

用左闭右开搜索区间[first, last)，

区间为空时终止并返回first或last(重合，无需纠结)，

求中点时从下界first(闭区间侧)出发: mid = first + (last - first) / 2，

以确保区间长度为1时，mid = first仍在[first, first + 1)区间内；

ii) 求上界（找满足x < value 或 x <= value条件的最大x的位置），可以调用互补的求下界的函数再减一得到，如x >= value的下界再减一就是x < value的上界，所以C++标准库只提供求下界的两个函数。

如果非要写（不推荐），则是求下界的镜面情况，把所有数组下标反过来即可：

用左开右闭搜索区间(first, last]，

区间为空时终止并返回last或first(重合，无需纠结)，

求中点时从上界last(仍为闭区间侧)出发: mid = last - (last - first) / 2，

以确保区间长度为1时，mid = last仍在(last - 1, last]区间内。

中点mid有了，怎样缩小区间才能不出错？

请往下看到"四、while loop的循环不变量"ヽ(ﾟ▽ﾟ)ノ有图有真相

（以下为详细解说，括号内的斜体为C++相关的选读(逃)）

二、Dijkstra的干货/题外话

为什么区间要写成左闭右开？怕傻傻分不清楚，一直用两头闭区间？

其实我们早就习惯了左闭右开区间，只不过你忘了它的便利。

例如：遍历长度为n的数组，下标i你是怎么写的？

你一定是使用左闭右开区间[0, n)作为起始和终止条件，这样一来循环执行次数为n，for loop结束时i == n，一目了然，且无需多余的 边界调整：

       for (size_t i = 0; i < n; ++i) {     // i is in [0, n) }     

换成Python 3，区间则是range(start, stop[, step])，左闭(包括起点start)右开(不包括终点stop)：

       for i in range(n):     # 等价于range(0, n)或range(0, n, 1)     # i is in [0, n)     

同理的还有Python的slice，如list slicing:arr[start:stop]以及arr[start:stop:step]。

一切始于图灵奖得主Dijkstra（没错就是20分钟内不用纸笔发明Dijkstra's Algorithm的那位神人）早在1982年的安利(他还安利过goto有害论，并且成功了)，大意是：

假设有一个长度为4的数组，用整数边界的区间表示它的下标0, 1, 2, 3，有四种写法：
a) 0 ≤ i < 4
b) -1 < i ≤ 3
c) 0 ≤ i ≤ 3
d) -1 < i < 4
显然左边不闭的话-1太丑了，所以只考虑a)和c)，然后怎么取舍呢？
现在假设该数组长度慢慢减小到0，右边界减小，此时它的index范围是空集 ，整数边界的区间的四种写法变成了：
a) 0 ≤ i < 0
b) -1 < i ≤ -1
c) 0 ≤ i ≤ -1
d) -1 < i < 0
现在只有a)不会出现负数了。看来左闭右开的a)是唯一一种不反人类的写法！它还有一些个好处：
1. 区间两端值的差，如[0, 4)中的4 - 0 = 4，正好是区间或数组的长度
2. 刚好相邻的区间，如[0, 2)和[2, 4)， 中间值（即2）相同，一眼就可以看出来

综上，代码中使用a)的左闭右开区间既符合直觉，又可以省去代码中大量的+1和-1和edge case检查，减少off-by-one error，提高效率。

三、while loop第一行：如何取中点

现在我们知道lower_bound在干啥，以及为啥区间要写成左闭右开了。

我们来看循环第一行，mid = first + (last - first) // 2，为何中点这么取？

       def lower_bound(array, first, last, value):     while first < last: # 搜索区间[first, last)不为空         mid = first + (last - first) // 2  # 防溢出         if array[mid] < value: first = mid + 1         else: last = mid     return first  # last也行，因为此时重合     

如 @胖君 等大佬们所言，

若用mid = (first + last) / 2算中点（下标的中位数），在C++、Java等语言里(first + last)可能会溢出。
讽刺的是，这是多年以前的标准写法，且问题存在了20年都没被发现，比如Java标准库java.util.Arrays里的binarySearch，因为当年的硬件限制了数组长度，所以测试的时候没有溢出。
解决方案就是我们的写法。评论区有人问为什么可以这么写，其实很简单：
mid = (first + last) / 2
= (2 * first + last - first) / 2
= first + length / 2，
其中length = last - first为区间长度。
Python有big integer所以不怕溢出，但要记得Python 3 的整除是//。

此外，中点的选择并不唯一：
1. 上位中位数：upperMid = first + length / 2 （不用-1，就它了）
2. 下位中位数：lowerMid = first + (length - 1) / 2

不难发现只有length为偶数时它们才不同，分别是中间那一对下标中的更大和更小的，想想[0, 3)和[0, 4)就很好懂了。

由于这两个中位数都在区间[first, last)内，所以都可以采用。算上位中位数不用-1，就是你了！

陷阱: 当我们使用左开右闭区间(first, last]找上界时，闭区间在右侧！本文开头已经说明，算中点时应从闭区间一侧向中心靠拢：

mid = last - (last - first) / 2

以确保区间长度为1时，mid = last仍在(last - 1, last]区间内

如果不小心写成mid = first + (last - first) / 2 那么此时mid = first就超出(first, last]范围了，要么溢出要么死循环！

所以推荐用互补的求下界的函数，再减一得到上界。

四、while loop的循环不变量 - loop invariants

（怎样缩小区间才不出错）（会写代码 vs 会用计算机科学的思考方式）

要真正理解这6行代码为啥能出正确答案，并每次写binary search都能bug free(而不是靠先写错再debug，或者死记硬背上/下界开/闭区间的四种情况，甚至其他答案说的区间长度小于一定值时暴力分类讨论)，首先需要理解while循环里的loop invariants (循环不变量)，也就是代码跑到while里面时一定成立的条件（别怕，下面有图）：

1. 搜索范围[first, last)不为空，即first < last ；
2. 搜索范围[first, last)左侧，即[first0, first)内所有元素(若存在)，都小于value，其中first0是first的初始值；
3. 搜索范围[first, last)右侧，即[last, last0)内所有元素(若存在)，都大于等于value，其中last0是last的初始值。

再看一遍代码：

       def lower_bound(array, first, last, value):     while first < last: # 搜索区间[first, last)不为空         mid = first + (last - first) // 2  # 防溢出         if array[mid] < value: first = mid + 1         else: last = mid     return first  # last也行，因为此时重合     

(图来啦)举个栗子，搜索整个array = [-1, 0, 0, 3, 3, 3, 7, 8, 9]，value = 3

一开始黄色的搜索区间左右(青、紫)都是空的，loop invariants的2和3自然满足。

上图array[mid] >= 3，说明mid属于紫色！

在已知信息下，最大限度合理扩张紫色区间、缩小黄色搜索区间长度的操作是：

把last放到上图中mid的位置，即last = mid ：

如上图，新的mid满足array[mid] < 3，说明mid属于青色！在已知信息下，最大限度合理扩张青色区间、缩小黄色搜索区间长度的操作是：first = mid + 1：

现在搜索区间长度缩短到1了！可以返回first了吗？不行，我们检查过了红圈左边和右边，却没有检查红圈本身。如果红圈是2，那么答案应该是上图的last才对。

之所以更新first或last的时候要最大限度缩小搜索区间（first更新为mid + 1而非弱一点的mid，last更新为mid而非弱一点的mid + 1），主要考虑并不是这个效率efficiency，而是上图区间长度为1的情况！此时mid就是first，mid + 1就是last，于是弱一点的更新等于没有更新，会导致死循环！

最后一步，上图中array[mid] >= 3，mid属于紫色，于是last左移一位，搜索结束：

最后区间[first, last)为空，青区间和紫区间都最大限度扩张了。所以，根据紫区间的定义任意元素 >= 3，已经饱和的它，第一个元素(若存在)的位置last就是答案！若没有满足要求x >= 3的元素，那么紫区间就是空的，停留在初始状态[last0, last0)，所以返回的是last0，即初始范围之后的第一个元素，表示“不存在”，无需特殊处理！

皆大欢喜的是，first与last重合，所以完全不需要纠结返回哪个！感谢Dijkstra！

五、C++中的相关函数

C++的lower_bound()搞明白了，那么upper_bound()和equal_range()又是怎么回事呢？

upper_bound() 和 lower_bound()一样是下界搜索，唯一不同的是第四行的if中的判断条件从：

lower_bound() 的 array[mid] < value，即小于，

变成了 upper_bound()的!(value < array[mid])，即array[mid] <= value，（用小于号判断小于等于关系：前面提到小于号是STL唯一的比较函数，且可以自定义）

所以upper_bound()返回的是第一个大于value的位置。

如此一来，[first, last)中与value 等价的元素的范围就是：

[lower_bound(value), upper_bound(value))

它们分别是这个区间的(左闭)下界和(右开)上界，因此得名。equal_range(value)的作用是同时返回这两个位置。

六、理解并使用C++<algorithm> 和Python bisect的二分查找函数

如何用lower_bound/bisect_left和upper_bound/bisect_right在[first, last)完成所有四种binary search (上/下界，开/闭区间)？

1. lower_bound(value)本身找的是x >= value的下界，若为last则不存在；
2. upper_bound(value)本身找的是x > value的下界，若为last则不存在；

因为区间是离散的，所以：

3. lower_bound(value) - 1 即为x < value的上界，若为first - 1则不存在；

4. upper_bound(value) - 1 即为x <= value的上界，若为first - 1则不存在。

相应代码可以参考 @LightGHLi 的高赞回答末尾。注意实际在C++中调用时，表示位置的first,last以及返回值不是Python代码中的下标int，而是Container<T>::iterator类型。

我推荐一下我的写法：

       def bsearch(a, f, left, right):     """     寻找数组 a 在范围 [left, right] 中最后一个满足 f 的下标，如果没有，返回 left-1；     f 在数组 a 中是单调递减的：如果f(a[3])，那么 a[0], a[1], a[2] 一定也满足 f     """     while left <= right:         mid = left + (right - left) // 2         if f(a[mid]):             left = mid + 1         else:             right = mid - 1     return right     

这样写的好处有：

• 代码简单
• 绝对不会重复进行 的判断
• 理论最优：循环次数（判断次数） 满足：

具体解释如下：

对于一个数组 ，有一个判断函数 ，满足存在单调性关系：

也就是说，可以将数组分为左右两份，左侧的全部满足 ，右侧全部不满足 。

我们的目标是找到：

注意到：

而解决问题的关键就是在循环过程中保持(*)式始终成立。

我们下面来考虑如何实现这个函数 。

第一想法是这样的，代码 1：

       def bsearch(a, left, right, f):     while left <= right:         mid = left + (right - left) // 2         if f(a[mid]):             left = mid         else:             right = mid     return left     

但是这样是有问题的，它是完全无法处理边界条件的，甚至它是永远无法返回的。我们来进行进一步的思考。

满足关系：

因此我们只要考虑 两种情况。

可能性 1:

可能性 2:

对于 , 有三种可能性：

可能性 3:

可能性 4:

可能性 5:

这时我们发现, 如果我们执行代码 1, 除了可能性 5会转化为可能性 2之外, 其余四种情况都会陷入无限自身循环。 为此我们把代码修改成这样, 代码 2：

       def bsearch(a, f, left, right):     while left <= right:         mid = left + (right - left) // 2         if f(a[mid]):             left = mid + 1         else:             right = mid - 1     return right     

这样修改完代码后我们发现可能性 1 - 5, 及其下一状态分别为：

可能性 1:

可能性 2:

可能性 3:

可能性 4:

可能性 5:

我们发现, 可能性 3 的下一状态是可能性 1，可能性 4 的下一状态是可能性 2，可能性1、2、5的下一状态都是终结状态。并且我们发现, 再每一轮循环的结束我们一直保持如下循环不变式：

而终止时, 一定满足：

因此, 代码 2 的正确性得到了证明。

根据代码 2，很容易可以修改为各种需要的版本，默认假设数组单调递增：

情况一：

找到单调递增数组 取值为 的第一个下标，如果没有返回 -1：

直接调用API

       def search(a, left, right, value):     index = bsearch(a, lambda x: x < value, left, right)     if index + 1 <= right and a[index+1] == value:         return index + 1     else:         return -1     

不调用API：

       def search(a, left, right, value):     old_right = right     while left <= right:         mid = left + (right - left) // 2         if a[mid] < value:             left = mid + 1         else:             right = mid - 1     if left <= old_right and a[left] == value:         return left     else:         return -1     

情况而：

找到单调递增数组 取值为 的最后一个下标，如果没有返回 -1：

直接调用API

       def search(a, left, right, value):     index = bsearch(a, lambda x: x <= value, left, right)     if index >= left and a[index] == value:         return index     else:         return -1     

不调用API：

       def search(a, left, right, value):     old_left = left     while left <= right:         mid = left + (right - left) // 2         if a[mid] <= value:             left = mid + 1         else:             right = mid - 1     if right >= old_left and a[right] == value:         return right     else:         return -1     

---

附：

取 ，对应的 时，需要循环的次数：

       1  [1, 1] 2  [1, 2, 2] 3  [2, 2, 2, 2] 4  [2, 2, 2, 3, 3] 5  [2, 3, 3, 2, 3, 3] 6  [2, 3, 3, 3, 3, 3, 3] 7  [3, 3, 3, 3, 3, 3, 3, 3] 8  [3, 3, 3, 3, 3, 3, 3, 4, 4] 9  [3, 3, 3, 4, 4, 3, 3, 3, 4, 4] 10 [3, 3, 3, 4, 4, 3, 4, 4, 3, 4, 4] 11 [3, 4, 4, 3, 4, 4, 3, 4, 4, 3, 4, 4] 12 [3, 4, 4, 3, 4, 4, 3, 4, 4, 4, 4, 4, 4] 13 [3, 4, 4, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4] 14 [3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4] 15 [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]