二分查找

介绍

二分查找 binary search，也称为折半搜索、对数搜索，是用来在一个 有序数组 中查找某一元素的算法。

算法流程：以在一个升序数组中查找一个数为例。

每次考察数组当前部分的 中间元素
如果中间元素刚好是要找的，就结束搜索过程
如果中间元素小于所查找的值，那么左侧的只会更小，因此在右侧查找
如果中间元素大于所查找的值，同理，只需到左侧查找

时间复杂度：

平均时间复杂度 $O (\log n)$
最坏时间复杂度 $O (\log n)$

因为在二分搜索过程中，算法每次都把查询的区间长度减半，所以对于一个长度为 $n$ 的数组，最多会进行 $O (\log n)$ 次查找。

模板

整数二分

cpp

int binary_search(int start, int end, int key) {
    int ret = -1;
    int mid;

    while (start <= end) {
        mid = start + ((end - start) >> 1);   // 直接相加可能会溢出

        if (arr[mid] < key) {
            start = mid + 1;
        }
        else if (arr[mid] > key) {
            end = mid - 1;
        }
        else {
            ret = mid;
            break;
        }
    }

    return ret;
}

常用的模板一般是不需要 ret = -1 这种情况的。如果没有找到该元素，我们返回第一个大于它的元素的下标，之后再通过比对返回值和 key 是否相同来判断数组中是否存在该元素。

由此，二分查找也可以被定义为 查找数组中第一个 >= key 的元素下标。

很多语言都集成了这个函数：

C++ 代码

cpp

#include <algorithm>
using namespace std;

vector<int> nums = {1, 2, 3, 3, 5}

lower_bound(nums.begin(), nums.end(), val);  // 返回首个 >= val 的元素的迭代器，不存在就返回 end()
upper_bound(nums.begin(), nums.end(), val);  // 返回首个 > val  的元素的迭代器，不存在就返回 end()

Python 代码

python

import bisect

ls = [1, 2, 5, 5, 5, 7, 9]

index1 = bisect.bisect(ls, 5)         # 返回首个 > key  的元素下标
index2 = bisect.bisect_left(ls, 5)    # 返回首个 >= key 的元素下标
index3 = bisect.bisect_right(ls, 5)   # 同 bisect.bisect

print(f"index1 = {index1}, index2 = {index2}, index3 = {index3}")
# index1 = 5, index2 = 2, index3 = 5

我们可以看出，一般都会集成两个函数（同时需要自行保证单调性）：

返回第一个 >= key 的元素下标
返回第一个 > key 的元素下标

同样的，我们可以自行解决如下问题：

返回最后一个 < key 的元素下标：第一个 >= key 的元素下标 - 1
返回最后一个 <= key 的元素下标：第一个 > key 的元素下标 - 1

而如果需要我们手写，则可以分为四种写法：

闭区间
左闭右开区间
左开右闭区间
开区间

这里用 Python 实现全部四种写法，用其他语言实现其中一种。具体这种写法的正确性可以用 循环不变式 来证明，即 区间内始终是尚未经过判断的数，证明和思考过程可以看参考资料中的视频 —— 红蓝染色法。

Python 代码：闭区间

python

def lower_bound(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums) - 1     # 闭区间 [left, right]

    while left <= right:      # 区间不为空
        mid = (left + right) // 2
        
        if nums[mid] < target:
            left = mid + 1    # [mid + 1, right]
        else:
            right = mid - 1   # [left, mid - 1]
        
    return left # right + 1

解释：

[0: left - 1] 区间总是 < target，染成红色（循环不变式，因此 nums[left] 为所求）
[right + 1: ] 区间总是 >= target，染成蓝色
退出前一轮 left = right = mid
- 如果 nums[mid] < target 时，染成红色，left = mid + 1
- 如果 nums[mid] >= target 时，染成蓝色，right = mid - 1
- 此时 nums[left] 总被染成蓝色，因此是第一个 >= target 的数
- 当然 nums[right + 1] 也符合要求
一定要注意最后的 nums[left] 可能越界

Python 代码：左闭右开区间

python

def lower_bound2(nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)         # 左闭右开区间 [left, right)

    while left < right:       # 区间不为空
        mid = (left + right) // 2
        
        if nums[mid] < target:
            left = mid + 1    # [mid + 1, right)
        else:
            right = mid       # [left, mid)
        
    return left  # right

解释：

[0: left - 1] 区间总是 < target，染成红色
[right : ] 区间总是 >= target，染成蓝色
退出前一轮为 [left, left + 1)
退出时为 [left, left)，由于 [right : ] 区间为蓝色，因此 nums[left] 为所求

Python 代码：左开右闭区间

python

def lower_bound3(nums: List[int], target: int) -> int:
    left = -1
    right = len(nums) - 1              # 左开右闭区间 (left, right]

    while left < right:
        mid = (left + right + 1) // 2  # 由于向下取整导致只有一个元素的时候总是更新到左端点

        if nums[mid] < target:
            left = mid
        else:
            right = mid - 1
        
    return left + 1 # right + 1

解释：

[0: left] 区间总是 < target，染成红色
[right + 1: ] 区间总是 >= target，染成蓝色

Python 代码：开区间

python

def lower_bound4(nums: List[int], target: int) -> int:
    left = -1
    right = len(nums)         # 开区间 (left, right)

    while left + 1 < right:   # 区间不为空
        mid = (left + right) // 2
        
        if nums[mid] < target:
            left = mid        # (mid, right)
        else:
            right = mid       # (left, mid)
        
    return right # left + 1

解释：

[0: left] 区间总是 < target，染成红色
[right: ] 区间总是 >= target，染成蓝色
退出时为 (left, left + 1)

要注意，只有 左开右闭区间 写法中需要对 mid 做 上取整 处理，因为出口情况 (l, l+1] 时由于下取整会导致 mid = l，因此无法更新区间。

总结

我们要找的是 第一个蓝色

python

# 闭区间
[l, l + 1], mid = l =>
[l, l] or [l + 1, l + 1]

# 左闭右开区间
[l, l + 1), mid = l =>
[l, l) or [l + 1, l + 1)      # 此时 l + 1 确定为蓝色

# 左开右闭区间
(l, l + 1], mid = l + 1 =>
(l, l] or (l + 1, l + 1]      # 此时 l 确定为红色

# 开区间
(l, l + 2), mid = l + 1 => 
(l, l + 1) or (l + 1, l + 2) # 此时 l 确定为红色，l + 2 确定为蓝色

C++ 代码：左闭右开区间

cpp

int lower_bound(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left < right) {
        int mid = left + (right - left) >> 1;

        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid;
        }
    }

    return left;
}

浮点数二分

浮点数二分就比较简单了。一般有：

循环 100 次，等价于区间缩短为原先的 1/2^100
区间长度小于 1e-6 后停止

这两种终止方法。

cpp

double l = -10000;
double r = 10000;

while (r - l > 1e-8) {
    double mid = (l + r) / 2;
    
    if (mid * mid * mid >= n) {
        r = mid;
    }
    else {
        l = mid;
    }
}

二分答案

三分法

其他

参考资料：

二分查找

模板题目：

力扣题目：

其他题目：

二分答案

力扣题目：

洛谷题目：

P1873 [COCI 2011/2012 #5] EKO / 砍树

其他题目：

三分法

洛谷题目：

P3382. 三分法 - 模板

011-二分查找

012-二分答案

013-三分法

041-单调栈

051-单调队列

二分查找

介绍

模板

整数二分

浮点数二分

二分答案

三分法

其他

二分查找

二分答案

三分法

最小化最大值

最大化最小值

二分查找 ​

介绍 ​

模板 ​

整数二分 ​

浮点数二分 ​

二分答案 ​

三分法 ​

其他 ​

二分查找 ​

二分答案 ​

三分法 ​

最小化最大值 ​

最大化最小值 ​

二分查找

介绍

模板

整数二分

浮点数二分

二分答案

三分法

其他

二分查找

二分答案

三分法

最小化最大值

最大化最小值