搜索与lower_bound/upper_bound边界处理)
如果你写过一段时间代码，大概率有过这种经历：数据量小的时候，for循环从头扫到尾什么问题都没有，可一旦数据涨到十万、百万级，同一个函数肉眼可见地慢下来。我之前在某个模拟项目里处理百万级有序记录，最开始用的线性查找，接口响应时间一直压不下去，改成O(log n)的二分查找之后，单次查询比较次数从几十万级直接掉到二十多次。这篇文章就把二分查找从底层原理、标准模板、边界处理，到进阶的lower_bound/upper_bound和二分答案一次讲透，适合所有想把查找和搜索写得更快的开发者，看完就能直接上手写代码。
1. 数据量一上来，线性查找第一个撑不住
1.1 一张表看清线性查找与二分查找的真实差距
不管你是写Python、Java、C++还是JavaScript，最常见的查找代码往往长这样：
def linear_search(nums, target): for i, num in enumerate(nums): if num == target: return i return -1线性查找的平均比较次数是 n/2。数据量小的时候感觉不到问题，n=10的时候平均比较5次，二分查找最多4次，差距几乎可以忽略。可一旦n变大，差距是指数级的。
| 数据规模 n | 线性查找平均比较次数 | 二分查找最多比较次数 |
|---|---|---|
| 10 | 5 | 4 |
| 1,000 | 500 | 10 |
| 100,000 | 50,000 | 17 |
| 1,000,000 | 500,000 | 20 |
| 1,000,000,000 | 500,000,000 | 30 |
这组数字值得反复看几遍。n等于10亿时，线性查找平均要比较5亿次，而二分查找最多30次就出结果，差了不止一千万倍。我见过一个内部模块，为了在内存里匹配大量来源记录，直接写了个for循环挨个扫，峰值流量一来CPU被打满，整个进程响应变慢。后来改成二分，同样的机器，CPU占用掉了一个数量级。这不是代码风格问题，是算法选择问题。
1.2 有序数组不是前提限制，而是额外信息
很多初学者会问：二分查找要求数组有序，但排序本身是O(n log n)，那我为什么不直接用线性扫？这个问题很合理，但得分情况。
如果同一份数据只查一次，先排序再二分确实不划算。可真实场景里，一份数据往往要被查成千上万次。比如用户输入了一百个关键词去匹配一个词典库，先排一次序花掉O(n log n)，后面每一次查询都是O(log n)，整体成本远低于每次都从头线性扫。更常见的情况是，数据本身天然有序：商品ID、时间戳、字典序、价格排序，根本不需要额外排序。
我之前也一度把"必须有序"当成二分的缺陷，后来想明白了：有序不是限制，而是你手里多了一张底牌。线性查找浪费了这个信息，每比较一个元素只排除一个候选；二分查找利用了这个信息，每比较一次就排除当前区间的一半。同样一份数据，用不同算法，复杂度直接就差了一个量级。
2. 二分查找为什么能把搜索砍到O(log n)：一次排除一半的数学直觉
2.1 猜数字游戏里的区间收缩逻辑
如果你玩过"我心里想了一个0到100之间的数，你猜完我告诉你高低"的游戏，那二分查找你已经懂了。最优策略是先猜50：如果高了，答案一定落在[0,49]；如果低了，答案一定落在[51,100]。每一轮都能把可能范围缩小一半，最多7次就能锁定答案，因为2^6=64，2^7=128，100在6到7次之间。
这个游戏的重点不是猜得准，而是每一轮都把不可能的区域整个扔掉，同时保证答案永远留在当前区间里。写二分查找时，脑子里一定要绷着一根弦：当前区间[left, right)是"答案可能存在的地方"，区间收缩的操作不允许把答案排除出去。我在改别人代码时见过不少诡异bug，target明明就在数组里，最后返回-1，原因基本都是区间收缩时把答案所在位置跳过去了。
2.2 从T(n)=T(n/2)+O(1)理解O(log n)
二分查找每一轮做常数次比较，然后进入规模减半的子问题，所以递推关系是T(n)=T(n/2)+O(1)。展开看：
T(n)=T(n/2)+1 =T(n/4)+1+1 =T(n/8)+1+1+1 ... =T(1)+log2(n)
因为n每除以2一次，就多一轮，直到n缩小到1，总共约log2(n)+1轮。这也是为什么n=10亿时只需要约30次比较：log2(10亿)约等于29.9。
有人纠结log的底数，其实无所谓。不同底数之间只差一个常数倍，都是O(log n)。这个量级最反直觉的地方在于：线性查找的代价是随n线性涨的，二分查找的代价是n翻倍才多一次比较。数据越大，二分优势越明显。拿本1000页的书举例，线性查找是逐页翻，二分查找是根据页码直接撕掉一半再撕掉一半，很快就锁定了。
3. 标准二分模板手写：我推荐左闭右开，附逐行解读
3.1 左闭右开模板代码逐行拆解
二分查找有很多种写法，有人用左闭右闭，有人用左闭右开，有人用递归。我最终固定下来的是左闭右开，因为它在处理变体问题时心智负担最小，不容易搞出"差一错误"。
def binary_search(nums: list[int], target: int) -> int: left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid return -1逐行说几个关键点。
left, right = 0, len(nums)表示当前查找区间是[left, right)，left可以取到，right取不到。这个区间模型一旦定下来，后面所有更新规则都要跟它匹配。
while left < right表示区间不为空。当left等于right时，说明区间已经空了，循环结束。这个条件不要随意改成left <= right，因为那是左闭右闭区间模型的条件，混着用很容易出问题。
mid = left + (right - left) // 2取的是左中位数。当区间长度为2时，mid会落在左边那个位置。配合下面的left = mid + 1和right = mid，可以保证每一轮区间都在缩小，不死循环。
三路比较的逻辑很直接：命中就返回；nums[mid]小于target，说明mid及其左边所有元素都可以排除，left跳到mid+1；nums[mid]大于target，说明mid及其右边所有元素都可以排除，但因为right本身不包含在区间里，所以right直接设成mid就够了，不需要再减1。
3.2 为什么mid必须写成left + (right-left)//2
很多人图省事写mid = (left + right) // 2，在Python里跑没问题，但这个习惯在C++或Java里是隐患：当left和right都接近int上限时，left + right会直接溢出，mid算出一个负数，数组就越界访问了。写成left + (right - left) // 2，先做减法再做加法，永远不会溢出。
还有一种写法是mid = (left + right) >> 1，用右移代替除以2。右移本身没问题，但括号里先算加法，溢出风险跟(left+right)//2一样。所以最稳妥的还是left + (right - left) // 2。
另外一个细节是取左中位数还是右中位数。左闭右开模板里，我固定用左中位数，也就是(right - left) // 2。如果改成(right - left + 1) // 2取右中位数，那配套的更新规则必须改成left = mid，否则会出现区间不收敛的情况。模板最怕混搭，取中位数的方式和更新方式必须是一套的。
3.3 死循环是怎么产生的：错误代码现场演示
我见过最多的问题代码长这样：
def buggy_search(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid # 错误：应该写成 mid + 1 else: right = mid return left if left < len(nums) and nums[left] == target else -1拿nums=[1,3,5]，target=3走一遍：left=0，right=3，mid=1，nums[1]=3不小于target，所以right=1；此时区间变成[0,1)，mid=0，nums[0]=1小于target，于是left=0。发现没有？left从0变成0，区间没有任何收缩，下一次循环又回到相同的状态，死循环。
原因就是mid取的是左中位数，当区间长度为1时mid正好等于left，此时如果你让left = mid而不是mid+1，left就原地踏步。这是二分最常见的死循环来源。
另一种错误是把右边界更新成right = mid - 1还觉得自己写得挺顺：
def buggy_search2(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 # 错误：和区间模型不匹配 return -1这个代码在target恰好不在数组里时可能碰巧返回-1，但一旦target在左边界附近，就可能因为right收缩过头而错过正确答案。我拿nums=[1,2,3]，target=1演示：left=0，right=3，mid=1，nums[1]=2大于1，right变成0；此时left=0，right=0，循环退出，返回-1，但target明明就在下标0。这就是区间模型混用的代价。
所以我的建议很简单：选一套模板，就把它的循环条件和更新规则一起背熟。左闭右开就永远是left < right、right = mid、left = mid + 1，不要临时"优化"。
4. 变体一网打尽：第一个等于、最后一个等于、lower_bound与upper_bound
4.1 先搞懂lower_bound和upper_bound
标准三路二分只能帮你找到任意一个等于target的位置。如果数组里有重复元素，比如[1,2,2,2,3,4]，你想知道第一个2在哪、最后一个2在哪，三路二分就力不从心了，因为你一命中就直接返回，根本不知道前面还有没有相同的值。
这时候要用的是lower_bound和upper_bound这两个概念。lower_bound(nums, target)返回第一个不小于target的位置，也就是第一个满足nums[pos] >= target的下标。upper_bound(nums, target)返回第一个大于target的位置，也就是第一个满足nums[pos] > target的下标。C++标准库里就有lowe_bound和upper_bound，Python的bisect模块则提供了功能对应的bisect_left和bisect_right。
这两个函数解决的不是"找任意一个"，而是"找边界"。有了它们，第一个等于target、最后一个等于target、第一个大于target、最后一个小于target都能轻松推出来。
4.2 第一个等于target：基于lower_bound一行完成
先手写一个lower_bound，代码和标准二分几乎一样，只改了一个地方：
def lower_bound(nums: list[int], target: int) -> int: left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] >= target: right = mid else: left = mid + 1 return left关键差异在比较条件上。标准二分是nums[mid] == target直接返回，而lower_bound遇到nums[mid] >= target就把右边界拉到mid。为什么？因为当mid位置的值大于等于target时，mid本身可能就是target，或者target一定在mid左边，总之一个满足条件的候选位置出现了，它可能在mid或者在更左边，所以把右边界收到mid，而不是mid-1。当mid值小于target时，mid肯定不满足条件，直接排除，left跳到mid+1。
循环结束后，left停的位置就是第一个nums[pos] >= target的地方。要找第一个等于target，只需要拿到这个位置后检查一下：
def search_first(nums, target): pos = lower_bound(nums, target) if pos < len(nums) and nums[pos] == target: return pos return -1用[1,2,2,2,3,4]，target=2验证：lower_bound返回1，nums[1]==2，所以第一个2在下标1。如果target=5，lower_bound返回6，pos等于len(nums)，说明数组里所有元素都小于5，返回-1。
4.3 最后一个等于target：基于upper_bound一行完成
upper_bound的代码同样只有一行条件差异：
def upper_bound(nums: list[int], target: int) -> int: left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] > target: right = mid else: left = mid + 1 return left这里用的是nums[mid] > target。为什么等于target时不收缩右边界？因为我们想找的是"第一个大于target的位置"，只要nums[mid]还等于target，说明它不够大，得继续往右找，所以left=mid+1。只有当nums[mid]已经大于target时，才说明这个位置可能是答案，收缩right到mid。
循环结束后，left停的位置是第一个大于target的下标。那么最后一个等于target的位置自然就是left-1：
def search_last(nums, target): pos = upper_bound(nums, target) if pos > 0 and nums[pos - 1] == target: return pos - 1 return -1用[1,2,2,2,3,4]，target=2验证：upper_bound返回4，pos-1=3，nums[3]==2，所以最后一个2在下标3。如果target=1，upper_bound返回1，pos-1=0，nums[0]==1，返回0。
4.4 变体记忆法：写清楚收缩条件再动笔
我不建议死记硬背每个变体的完整代码，因为变体一多，很容易背串。我的记忆方法是只记两句话：
- 找第一个满足条件的位置：用lower_bound，收缩条件写
nums[mid] >= target，最后返回left。 - 找最后一个满足条件的位置：用upper_bound，收缩条件写
nums[mid] > target，最后返回left-1。
其他边界问题都可以从这两个函数组合出来。比如"最后一个小于target的位置"就是lower_bound(target)-1，"第一个大于target的位置"就是upper_bound(target)本身。写代码之前先把收缩条件写出来，想清楚"当mid满足什么条件时，答案可能还更左"再动手，基本不会错。
5. 二分不止用于查找数组：二分答案的check思维才是进阶关键
5.1 从猜下标到猜答案：二分答案的通用套路
二分查找最常见的形态是在数组里查找元素，这是"猜下标"。但二分的适用范围远不止此，它还能直接猜答案本身。这个方法有个常见的叫法：二分答案。
适用场景是这样的：有一个问题的答案落在某个数值区间[L, R]里，直接枚举L到R的每个值太慢，但我们能快速判断某个值mid作为答案是否可行，并且答案的可行性是单调的。此时就可以把L到R看成一个有序数组，用二分在上面搜索满足条件的答案。
通用套路就三步：
- 确定答案的范围[L, R]；
- 写一个check(mid)，判断mid作为答案是否可行；
- 根据check(mid)的结果调整区间，最后得到最优答案。
判断能否用二分答案，核心就看单调性：当mid变大时，check结果是不是一直保持"可行"或"不可行"，不会来回跳变。如果答案是单调递增或单调递减的，就能二分；如果忽好忽坏，二分直接失效。
5.2 check函数怎么写：找到单调关系
拿一个很经典的例子说明：把若干根木头切成k段，每段长度必须相等，问每段最大能有多长。设答案长度为x，能切的段数是sum(wood_i // x)。这里的关系是：x越小，能切的段数越多；x越大，能切的段数越少，这是个单调递减关系。
如果答案可行，意味着段数至少是k；段数更多当然也没问题。所以check函数这么写：
def check(mid): if mid == 0: return False return sum(w // mid for w in woods) >= k这个例子很好地说明了"单调关系"很重要。长度越大，可切段数越少，所以随着mid增大，check从true变成false。我们想找的是满足check(mid)为true的最大mid。写二分时，只要把check函数看成"数组里某位置的值"，问题就变回了熟悉的二分查找。
5.3 两种二分答案实现：整数版与浮点版本
整数二分答案经常用左闭右闭模板，因为答案范围是离散的整数，可以放心用mid+1和mid-1：
def max_wood_len(woods, k): def check(mid): if mid == 0: return False return sum(w // mid for w in woods) >= k left, right = 1, max(woods) while left <= right: mid = left + (right - left) // 2 if check(mid): left = mid + 1 # 长度还可以更大 else: right = mid - 1 # 长度太大，往回缩 return right注意这里的终止条件是left <= right，和前面左闭右开不同，因为这是闭区间模型。当check(mid)为true时，答案可能是mid或比mid更大，所以left变成mid+1；为false时，答案只能在mid左边，right变成mid-1。循环结束后right就是最大可行值。
浮点二分答案也很常用，比如求平方根：
def sqrt_binary(x, eps=1e-8): if x < 0: return -1 left, right = 0.0, max(1.0, x) while right - left > eps: mid = (left + right) / 2 if mid * mid < x: left = mid else: right = mid return (left + right) / 2浮点版本和整数版有个重大区别：不能用mid+1或mid-1，因为浮点数连续，那样会跳过正确答案，甚至陷入死循环。终止条件也不是left == right，而是区间长度小于某个精度eps。工程上eps一般取1e-6到1e-8，太小了double浮点数精度也撑不住。另外，千万不要用mid * mid == x判断相等，浮点数误差会让这个条件永远不成立。
6. 实战复盘：我踩过的二分查找的坑和现在的编码习惯
6.1 三个让人头疼的历史bug复盘
第一个bug是循环条件写错。我在左闭右开模板里一度写过while left <= right，结果配合right = mid更新，在区间缩到只剩一个元素时反复进入循环，最后直接超时。排查了很久才发现是区间模型混用了。从那以后我给自己立了规矩：左闭右开就永远是left < right，不要看到别人用left <= right就随手改。
第二个bug是在变体里直接套标准三路模板。当时要在重复元素数组里找第一个等于target的位置，我拿着标准二分改了半天，发现nums[mid] == target的时候直接返回，目标位置并不一定是最左边的。后来换用lower_bound的思路，把相等分支改成收缩右边界，才真正解决问题。
第三个bug是二分答案的check方向写反了。切木头问题要求"最多长度"，我一开始写的check条件是sum(w // mid) <= k，结果答案永远是最大值。后来我把段数和长度的关系画在纸上，发现长度越大段数越少，可行条件应该是段数大于等于k，方向一改就对了。
6.2 稳定高效的自测与调试流程
二分代码写完一定要自测，我一般用这张表把所有边界都覆盖一遍：
| 场景 | 输入 | 期望结果 |
|---|---|---|
| 空数组 | [], 1 | -1 |
| 单元素命中 | [1], 1 | 0 |
| 单元素未命中 | [1], 2 | -1 |
| 命中在开头 | [1,2,3], 1 | 0 |
| 命中在结尾 | [1,2,3], 3 | 2 |
| 目标小于所有元素 | [1,2,3], 0 | -1 |
| 目标大于所有元素 | [1,2,3], 4 | -1 |
调试时最笨也最有效的方法是在while循环里打印left、right、mid三个值。如果连续两轮循环left和right完全没有变化，基本可以断定是left = mid导致的不收敛。另外，我习惯在写完一个变体后顺手跑一遍lower_bound的用例，再跑一遍upper_bound的用例，两个方向都验证过才放心。
6.3 我对二分模板的最终建议
我现在的编码习惯是：日常查找单个元素用左闭右开三路模板；遇到重复元素或边界衍生问题，直接用lower_bound和upper_bound组合，不自己另写变体；二分答案题先判断单调性，再写check函数，最后把check结果随mid变化的趋势画出来确认方向。
老实说，二分写得少的人一开始确实会觉得边界很绕，这不是你笨，而是因为你没有固定一套区间模型。与其每次临场推演，不如选一套自己顺手的模板，把循环条件和更新规则练成条件反射。我最终选左闭右开，只是因为它处理变体时心智负担最小。你完全可以选左闭右闭，但写之前先把区间定义写在注释里，不要脑子一热就开写。把这一套模板练到形成肌肉记忆，以后再遇到有序数组和单调问题，你的第一反应就会是O(log n)的二分，而不是老老实实从头扫一遍。
