开始前，会这些就够了
- 会运行一小段 Python，认识字符串、列表和条件判断即可
遇到不熟悉的词，先看这 1 个解释
- 二分查找
- 在有序数据里，每次比较中间位置，把已经确定不可能包含目标的一半排除。重复这个过程，剩余范围会越来越小。能排除哪一半，依赖数据遵守同一套排序规则。
找一本按名字排好的通讯录，你大概不会从第一页一直翻到底，而会先看中间，再决定往哪边找。这个省事办法靠的不是“中间”有什么魔力，而是前后的顺序提供了可靠线索。
如果通讯录被人随意打乱，看见中间的名字比目标靠后，并不能说明目标在左边。二分查找也一样：每次排除一大块之前，要能解释为什么那块不可能有答案。少比较几次不等于判断正确。
每次扔掉一半，凭什么不会扔错？
先找第一个“大于等于目标”的位置，再检查这个位置是不是刚好等于目标。待比较区间写成 [左, 右)：包括左边，不包括右边。右边界虽然不用再比较，仍可能是最后的答案。
- 下标 03待比较
- 下标 17待比较
- 下标 27待比较
- 下标 312下次比较
- 下标 418待比较
- 下标 525待比较
- 下标 631待比较
已比较 0 次，当前区间 [0, 7)。下一次比较下标 3 的 12。
有序例子含两个 7，找下界会停在第一个 7。返回数组长度是一个位置标记，不能直接当作有效下标读取；这里不包含排序的时间成本。
先把问题改成：第一项不小于目标的在哪？
我们固定一个任务：在从小到大排列的列表里，找到第一项大于或等于目标的位置。它常被称为左边界。假设列表是 3、7、7、12、18、25、31，找 7 时不能遇到任意一个 7 就停，还要确认左边是否有另一个符合条件的数。
这个定义也处理不存在的目标。比如插入一个新值时，左边界就是保持顺序的一个插入位置；若所有值都比目标小，结果可以等于列表长度，表示放在末尾。这个位置并不是一个可直接读取的现有元素。
有序，才能把一次比较推广到半个列表
当中间值小于目标时，它以及左边所有值都太小，因此可以一起排除。如果中间值已经不小于目标，它可能是答案，但更左边也可能符合条件，所以保留中间位置并继续缩小左侧范围。重复值不会破坏这个判断。
这里的“有序”还要求排序与查找使用相同的比较规则。按文字排好的数字字符串，不一定符合数值大小顺序；从大到小排的列表，也不能直接交给假定升序的版本。二分搜索更普遍的条件是判断结果只有一处转折，本篇只用升序数字来观察。
同样的函数，对两份名单会做什么？
Python 的 bisect_left 返回这种插入边界，不会替你检查整个列表是否有序。示例先测试含重复值、缺少目标和超过末尾三种情况。要判定“找到目标”，还需先确认位置没越界，再比较该位置的值。
最后故意打乱两个数：18 明明还在列表里，查找却可能错过。这个结果是违反前提后的一次具体表现，不能概括成“乱序时总返回某个固定错误”。错过目标也不是标准库应该负责替你排序。
from bisect import bisect_left
ordered = [3, 7, 7, 12, 18, 25, 31]
for target in [7, 8, 40]:
index = bisect_left(ordered, target)
found = index < len(ordered) and ordered[index] == target
print(target, index, found)
mixed = [3, 18, 7, 12, 7, 25, 31]
target = 18
index = bisect_left(mixed, target)
found = index < len(mixed) and mixed[index] == target
print("mixed", index, found, "actually_present", target in mixed)怎样运行：保存为 binary_search_demo.py，在一个自己的练习目录中运行 python binary_search_demo.py。使用 Python 3.9 或更高版本，仅用标准库。
运行后对照结果
7 1 True
8 3 False
40 7 False
mixed 5 False actually_present True查得快，还要算上维持顺序的费用
在可按下标直接访问的有序列表上，区间每次大约减半，所以比较次数增长很慢。但把一大堆乱序数据先排好，本身要做工作。如果只找一次，顺着看一遍未必不合算；如果要查很多次，事先整理才可能更值得。
找到插入位置快，也不代表插入本身快。数组式列表可能需要把后面的元素挪开。实际选结构时，要分开考虑查找、插入、删除和维持顺序的代价。这个小例子比较的是返回位置与前提，没有拿几次计时当成所有数据量的性能结论。
记住这三点
- 每次排除一半的理由来自顺序，而不是来自函数名字。
- 左边界是第一项不小于目标的位置；返回位置后仍要验证是否命中。
- 查找、排序和插入的代价要分开考虑。
别把例子用过头
- 含重复值仍可二分，但“第一个符合”和“任意命中”不是同一个任务。
- 返回列表长度是合法边界，直接读取它会越界。
自己试一小步
给左边界查找整理一组能发现错误的小输入。
- 覆盖空列表、单元素、全部相同、目标比所有数小和比所有数大。
- 在纸上逐轮记下还可能包含左边界的范围，再运行库函数对照。
- 自己打乱一份数据，指出哪次排除已失去可靠依据。
做到这些，就算完成
- 有序样本中，边界左侧都小于目标，右侧都大于或等于目标。
- 空列表和末尾位置不会被当成现有元素读取。
- 没有把乱序样本碰巧成功当成算法保证。
查原始资料
想确认一个细节，先看这份资料对应的部分，不必从头读完所有文档。
- bisect — Array bisection algorithm （新标签页）↗
支持
bisect_left的有序前提、左边界定义，以及查找和列表插入的复杂度区别。 - 10.1 二分查找 （新标签页）↗
支持有序数组中的区间缩小过程、效率与使用边界；本篇另用
bisect_left演示重复值。
找一份资料继续练
先选一项，按下面的范围继续学；不必从头读完整门课程。
Hello 算法：用图和 Java 理解数组、链表与查找 （新标签页）↗
只读二分查找，用含重复数字的有序数组逐次记录左右边界，并说明每次为什么能排除另一半。
查看学习准备与访问说明 →