二分查找利用单调性，每次排除一半搜索范围。使用前先确认两件事：答案落在一个明确的范围内，而且检查中间位置后，能确定哪一半范围可以舍弃。

在升序数组中找元素符合这个条件；寻找最小可行速度、最小容量等问题，也可以把答案范围作为搜索对象。常见的判断结果是：

False False False | True True True
                  ↑
              第一个满足条件的位置

基础查找：在有序数组中找目标

下面的 Python 模板维护闭区间 [left, right]，找到目标返回下标，找不到返回 -1。

def binary_search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

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

    return -1

例如在 [1, 3, 5, 7, 9, 11] 中找 7，第一次检查下标 2，对应的值是 5。因为 5 < 7，下标 0 到 2 都可以排除，接着只搜索右半部分。

闭区间在 left == right 时仍有一个元素，所以循环条件是 left <= right。比较后已经确认 mid 不可能是答案，就用 mid + 1 或 mid - 1 排除它。数组查找的时间复杂度为 O(log n)。

如果有重复值，这个模板返回任意一个匹配位置。需要第一个或最后一个位置时，要使用边界查找。

边界查找：第一个满足条件的位置

以 [1, 2, 2, 2, 4, 6] 为例，第一个 >= 2 的位置是下标 1。遇到 nums[mid] >= target 时，先记下这个候选答案，再继续往左找。

def lower_bound(nums, target):
    left, right = 0, len(nums) - 1
    answer = len(nums)

    while left <= right:
        mid = (left + right) // 2

        if nums[mid] >= target:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

返回 len(nums) 表示没有元素满足条件，这个返回值不能直接当作数组下标。把判断中的 >= 改成 >，就能寻找第一个严格大于目标的位置。

Python 的 bisect 模块已经封装了这两种边界查找：

from bisect import bisect_left, bisect_right

nums = [1, 2, 2, 2, 4, 6]
x = 2

left = bisect_left(nums, x)    # 1：第一个 >= x 的位置
right = bisect_right(nums, x)  # 4：第一个 > x 的位置

四种常见边界可以统一写成：

要找的位置	写法	上例结果
第一个 >= x	bisect_left(nums, x)	1
第一个 > x	bisect_right(nums, x)	4
最后一个 <= x	bisect_right(nums, x) - 1	3
最后一个 < x	bisect_left(nums, x) - 1	0

访问数组前要检查 0 <= index < len(nums)。特别是 -1 表示没有对应的左侧元素时，不能直接用 nums[-1]，否则会取到最后一个元素。

bisect 返回的是插入位置，查找某个值是否存在，还需要检查下标有效且 nums[index] == x。这些规则适用于升序数组，具体定义见 Python bisect 官方文档。

二分答案：把最优化问题变成可行性判断

题目问最小速度、最小容量或最少天数时，可以先定义 check(x)：使用答案 x，能否满足题目要求？

例如速度越大越容易完成任务，如果某个速度可行，更大的速度也都可行，判断结果就呈现 False…True。寻找最小可行速度，等价于寻找第一个 True。

整数答案范围 [left, right] 可以沿用闭区间模板：

def first_feasible(left, right, check):
    answer = None

    while left <= right:
        mid = (left + right) // 2

        if check(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer

这个模板要求 check 在搜索范围内单调地从 False 变为 True；如果范围内没有可行答案，返回 None。遇到 True…False、需要最大可行答案的题目，则在可行时记录答案并往右找，不可行时往左找。

做二分答案题时，最需要推敲的是答案上下界和 check 的单调性。二分只是反复调用这个判断。若范围有 R 个整数候选值，一次判断耗时为 T，总时间复杂度为 O(T log(R + 1))。

“最小化最大值”“最大化最小值”“至少”“至多”等描述可以提示我们考虑二分，但这些词本身不能证明问题具有单调性。

写二分时容易出错的地方

• 区间定义混用。闭区间 [left, right] 与半开区间 [left, right) 的初始化、循环条件和边界更新必须配套使用。上面的手写模板都采用闭区间。
• 搜索范围没有缩小。例如 left = 3, right = 4 时，mid = 3；若直接写 left = mid，下一轮范围不变，可能死循环。保留 mid 的写法只有在相应区间规则下才能使用。
• 找到一个可行位置就返回。寻找第一个满足条件的位置时，左侧可能还有答案，需要记录候选位置并继续搜索。
• 忽略返回值的边界。普通查找的 -1、边界查找的 len(nums)、二分答案的 None，都需要在后续使用前处理。

落笔前先写清楚：要找元素还是边界，搜索范围是什么，单调性为什么成立，以及判断 mid 后能排除哪一段。只要每轮都缩小范围，并且没有丢掉可能的答案，边界更新就有依据。