顺序查找与二分查找全解析：迭代、递归、边界变种与选型实战

二分查找这东西，第一次写就能一次跑通的人真不多。前阵子帮人看一段代码，题目是“在一个有序数组里找目标值”，对方洋洋洒洒写了二十来行，我扫了一眼只问了一句：“数组长度是 1 的时候，你这个 while 循环还进得去吗？”他愣了一下，跑了一遍，果然死循环。类似的事情我见过太多次了：顺序查找、二分查找的递归实现、二分查找的迭代实现，这三样东西几乎是每个人学编程最早接触的查找方法，也恰恰是最容易“以为自己会了”的地方。

查找这件事在业务代码里出现的频率高得惊人：配置表里找一个 key、日志里捞一个时间点、排行榜里定位某个分数段、分页查询里算偏移量。数据量小的时候怎么写都对，数据量一大、边界一刁钻，写法上的差异就全暴露出来了。下面我按“顺序查找 → 迭代二分 → 递归二分 → 二分变种 → 实测选型”这条线,把三种方法从头拆一遍，代码以 Python 为主，关键处会标注其他语言的差异。不管你是刚学算法的新手，还是写了几年业务代码但很久没碰过手写二分的老手，应该都能捞到点东西。

1. 顺序查找：被低估的“笨办法”，边界比你想的宽

1.1 顺序查找到底在做什么

顺序查找（也叫线性查找）的逻辑简单到不需要解释：从数组一头开始，一个一个比，相等就返回下标，走到头还没找到就返回不存在。它的时间复杂度是 O(n)，空间复杂度 O(1)，不需要数据有任何额外性质——排不排序都行，是不是数组都行，甚至数据在链表里、在文件流里、在数据库游标上，只要能“逐个往下走”，顺序查找就能用。

def sequential_search(arr, target): for i, value in enumerate(arr): if value == target: return i return -1

这七行代码是三种查找方法里唯一一个“不需要任何前置条件”的。二分查找要求数据有序，而排序本身的代价是 O(n log n)——如果你只需要查一次，先排序再二分，总代价比直接顺序扫一遍还高。这是很多人做选型时忽略的一点：二分的 O(log n) 是建立在“数据已经有序”这个前提上的，前提不成立时，它并不便宜。

1.2 什么时候顺序查找反而是最优解

我带过的新人里，有一种很典型的思维惯性：觉得二分比顺序快，于是不管什么场景都想往上套二分。实际工程里，顺序查找在下面这几种情况下是更优解，甚至是唯一解。

里面最容易被忽略的是链表那条。二分查找的核心动作是“跳到中间”，这要求 O(1) 的随机访问能力。链表要从头走 n/2 步才能摸到中点，一次“取中”就是 O(n)，整个二分退化成 O(n log n)，比顺序查找还慢。所以看到有人在链表上写二分，基本可以判断他没想清楚数据结构的约束。

1.3 哨兵优化：省掉一次边界判断

顺序查找最常见的优化叫“哨兵”。普通写法里每轮循环要做两次判断：i < n和arr[i] == target。哨兵的做法是在数组末尾（或开头）放一个必定能命中的值，这样循环里就只需要判断相等，边界判断被省掉了。

def sentinel_search(arr, target): n = len(arr) if n == 0: return -1 last = arr[n - 1] # 先把最后一个元素存起来 arr[n - 1] = target # 用目标值占位，充当哨兵 i = 0 while arr[i] != target: # 循环内只有一次比较 i += 1 arr[n - 1] = last # 还原现场 if i < n - 1: return i return last == target and n - 1 or -1

这个技巧在 Python 里收益很小，因为解释器开销远大于一次比较；但在 C/C++ 这类语言里，循环体内少一次分支判断，在百万级数据上能测出可观的差异。要注意的是哨兵会临时修改原数组，如果这段代码不是独占数组，或者数组是只读的（比如传进来的是 tuple、是共享缓存），就不能这么写。我在实际项目里见过有人在多线程环境下用哨兵，没加锁，结果另一个线程正好读到了被改成哨兵的最后一个元素，排查了很久。这类“为了性能偷的一步”一定要先确认数据的所有权。

1.4 顺序查找的几种实战变体

实际业务里很少是“找一个就返回”，更多是下面这几种形态，都得基于顺序扫描来写。

找全部匹配项：

def find_all(arr, target): return [i for i, v in enumerate(arr) if v == target]

按条件查找（找第一个满足条件的元素），这是最常用的形态：

def find_first_where(arr, predicate): for i, v in enumerate(arr): if predicate(v): return i, v return -1, None

从后往前找（找最近一次出现的）：

def find_last(arr, target): for i in range(len(arr) - 1, -1, -1): if arr[i] == target: return i return -1

最后这个变体在日志分析里特别常见——找某个事件“最近一次”发生的位置，从后往前扫往往几步就命中，比正向扫整个数组快得多。这里的经验是：顺序查找的复杂度是 O(n)，但常数因子取决于你从哪头开始扫。对数据分布有直觉的时候，选对扫描方向能带来数量级的实际差异。

2. 迭代版二分查找：先把区间定义钉死，再动手写

2.1 二分查找成立的两个前提

二分查找能成立，靠的是两个条件，缺一不可。

第一是单调性。数组必须是有序的（升序或降序），这样才能通过“中点值和目标值的比较”推断出目标只可能在左半边或右半边。注意这里说的是单调性而不是“有序”，因为二分不仅能用在排序数组上，还能用在任何单调函数上——比如“在 1 到 n 中找最小的满足 f(x) 为真的 x”，只要 f 是单调的，二分就能用。后面讲变种时会展开这一点。

第二是随机访问。必须能在 O(1) 时间内取到任意位置的元素，所以数据结构得是数组（或支持下标访问的容器），链表不行。

def binary_search_closed(nums, target): left, right = 0, len(nums) - 1 # 区间是 [left, right]，闭区间 while left <= right: # 区间非空时继续 mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 # 目标在右半，丢弃 mid 本身 else: right = mid - 1 # 目标在左半，丢弃 mid 本身 return -1

这十几行代码，我建议初学者背下来，背到能默写的程度。不是为了考试，而是因为它是后面所有变种的语法基础——左右边界的收缩规则、mid 的计算方式、循环终止条件，这三件事在变种里会以不同组合出现，基础写法不熟，变种一定写崩。

2.2 循环不变量：为什么这套 while 条件是对的

很多人写二分是靠“试”，改了这行不行就换那行，最后改对了也不知道为什么。正确的做法是抓住一个东西：循环不变量，也就是“每一轮循环开始时，区间里一定还包含答案”这个性质。

在上面闭区间的写法里，不变量是“目标如果存在，一定在[left, right]内”。于是：

• 循环条件必须是left <= right，因为当left == right时区间里还有一个元素，没检查完不能退出；如果写成left < right，就会漏掉最后一个元素。
• nums[mid] < target时，mid 位置肯定不是答案，所以新区间从mid + 1开始，而不是mid。
• nums[mid] > target时同理，新区间到mid - 1结束。

只要把这三条想清楚，代码就不需要试错。反过来，如果你写成了“左闭右开”的区间定义，那三条全都要跟着变：

def binary_search_half_open(nums, target): left, right = 0, len(nums) # 区间是 [left, right)，右开 while left < right: # 区间为空的条件是 left == right mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid # mid 本身不属于区间，所以是 mid 而不是 mid-1 return -1

两套写法都对，唯一的错误是混着写。我在代码评审里见过最常见的崩法就是：初值用了right = len(nums) - 1（闭区间），循环条件写成了left < right（开区间的条件），结果最后一个元素永远查不到；或者初值用了right = len(nums)，收缩时写了right = mid - 1，结果越界。这里没有玄学，只要问自己一句：“我现在维护的区间到底是开的还是闭的？”

2.3 mid 计算里的溢出坑与加法方向

mid = (left + right) // 2是教科书写法，但在 Java、C、C++ 这类有固定宽度整型的语言里，当left和right都接近INT_MAX时会整数溢出，变成负数，然后下标越界。正确写法是：

mid = left + (right - left) // 2

先做减法再除以 2，值不会超过right的范围。Python 的整数是任意精度，不会有这个问题，但写 Java 的时候必须用后者。我个人的习惯是无论什么语言都用后者，跨语言迁移代码时省得回头改。

还有一个细节：(right - left) // 2是向下取整，所以当区间长度为 2 时，mid会等于left。这意味着在某些变种里，如果收缩逻辑写成left = mid，就会死循环——因为 mid 没往前走。这是二分死循环的头号原因，后面会在变种部分重点讲。

2.4 一次完整的“二分死循环”排查链路

说个真实的排查过程，这类问题我觉得比直接给答案更有价值。某同学写的是“找第一个大于等于目标值的位置”，代码如下：

def bad_lower_bound(nums, target): left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left

问题是：当len(nums) == 0时，right = -1，循环进不去，返回left = 0，调用方拿去取nums[0]直接越界崩了。修复方式是统一改成左闭右开的写法，把right初始化为len(nums)：

def lower_bound(nums, target): left, right = 0, len(nums) # [left, right) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left # 区间内第一个 >= target 的位置，可能等于 len

这个过程的排查思路可以固化成三步：先想清楚区间定义 → 再验证空数组、单元素数组的行为 → 最后验证目标值不存在、目标值在首尾两端的行为。这四类用例能覆盖绝大多数二分 bug。我自己的习惯是在写二分的文件顶部放一个小测试函数，每次改完跑一遍，比肉眼审查可靠得多。

def _test_search(): cases = [ ([], 1, -1), ([1], 1, 0), ([1], 2, -1), ([1, 3, 5, 7, 9], 1, 0), ([1, 3, 5, 7, 9], 9, 4), ([1, 3, 5, 7, 9], 5, 2), ([1, 3, 5, 7, 9], 4, -1), ([1, 1, 1, 1], 1, None), # 重复元素，只校验能命中 ] for nums, target, expect in cases: got = binary_search_closed(nums, target) if expect is not None: assert got == expect, f"期望 {expect}，实际 {got}：{nums} 查 {target}"

注意：当数组里有大量重复元素时，普通二分返回的下标是“其中某一个”，具体是哪个取决于 mid 的落点，不要假设它返回第一个或最后一个。如果业务上需要确定的位置，必须用后面的边界查找写法。

3. 递归版二分查找：代码优雅，但有三个坑等着你

3.1 递归写法的骨架与状态传递

递归版二分的逻辑和迭代版完全一样，区别只在于“用函数调用代替循环来推进区间”。区间边界作为参数往下传，递归出口是区间为空或者命中目标。

def binary_search_recursive(nums, target, left=None, right=None): if left is None: left, right = 0, len(nums) - 1 if left > right: # 区间为空，说明不在这里 return -1 mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[mid] < target: return binary_search_recursive(nums, target, mid + 1, right) return binary_search_recursive(nums, target, left, mid - 1)

这里用left=None做默认值，是为了让调用方可以只传nums和target。如果你直接用left=0, right=len(nums)-1做默认参数，Python 会在函数定义时求值，而定义时nums还不存在，直接报 NameError。这个坑和“可变默认参数”是同一类问题，值得记一下。

3.2 一个反直觉的结论：递归深度根本不是问题

很多人不敢用递归版二分，理由是“怕栈溢出”。这个担心在二分查找里其实站不住脚——因为递归深度是 O(log n)，不是 O(n)。

具体算一下：100 万元素的数组，每次砍一半，从 1,000,000 砍到 1 只需要约 20 次，也就是说最大递归深度只有 20 层。就算数据量涨到 10 亿，深度也才 30 层。Python 默认递归限制是 1000 层，Java 默认栈在几百 KB 到 1MB 之间，20 层调用栈毫无压力。所以“递归二分会爆栈”这个说法，在正常数据规模下是不成立的。

真正让我不敢随随便便上递归的原因，是函数调用的开销。一次递归要保存现场、传递参数、返回结果，虽然每层很便宜，但二分本身总比较次数就少（log n 次），开销占比一下子就上去了。几百万次查询的场景下，递归版和迭代版的耗时差距能到 2 到 4 倍，具体取决于语言和解释器。这个差距在 Python 里尤其明显，因为解释器执行函数调用的成本比 C 高一个量级。

3.3 递归写法的三个真实隐患

第一个隐患是切片。这是我见过最严重的一个坑，新人特别容易这么写：

def bad_recursive(nums, target): if not nums: return -1 mid = len(nums) // 2 if nums[mid] == target: return mid if nums[mid] < target: sub = bad_recursive(nums[mid + 1:], target) # 每次切片都复制一份新列表 return -1 if sub == -1 else mid + 1 + sub return bad_recursive(nums[:mid], target)

逻辑上是通的，但nums[mid+1:]会复制出一份新列表。一次二分有 log n 层，第 k 层切片的长度是 n/2^k，把这些复制量加起来：n/2 + n/4 + n/8 + … 约等于 n。所以时间复杂度从 O(log n) 退化到 O(n)——虽然还是有进位，但每层的切片操作带着内存分配，实际表现比顺序查找还慢，空间上额外多出 O(n) 的临时列表。递归写二分的正确姿势是传下标，不传子数组。这条对 C++ 用vector切片、Java 用Arrays.copyOfRange全都适用。

第二个隐患是参数语义。递归版里“区间是开是闭”这件事被参数名稀释了，调用方看不出来。我的做法是把语义写进函数名或注释，比如_search_closed(nums, target, left, right)，一眼就知道右边界是包含的。团队协作里这种小命名比注释管用。

第三个隐患是尾递归优化不存在。二分递归的最后一层调用是“直接返回递归结果”，属于尾递归，理论上可以优化成循环，但 Python 和 Java 都不做尾递归优化。所以别指望写递归能自动变成迭代的性能，想快就老实用循环。

3.4 那什么时候该用递归版

既然迭代版又快又省，递归版还有存在价值吗？有，主要在两个场景。

一是题目本身是递归结构时，递归写法更贴合思路。比如“在二维矩阵的某一行里二分，找到目标后进入下一层判断”“在决策树上二分答案并递归验证”，这类问题的状态传递比较重，用递归把区间状态放在参数里，代码读起来反而清爽。二是教学和评审场景，递归版把“砍一半”的意图表达得更明确，讲解时更好懂。

我自己的工程习惯是：能迭代就迭代，需要把区间状态显式地往下传、或者跟其他递归结构组合时才用递归。这不是性能洁癖，主要是减少不确定性——迭代版只有一份状态，出问题一眼能看出来；递归版的栈帧是隐式的，出错时你得在脑子里重建整个调用链。

4. 二分的真正战场：边界查找与“猜答案”

4.1 lower_bound 与 upper_bound：两个模板打天下

普通二分只能回答“目标在不在、在哪”，但业务里更常问的是“目标应该插在哪”“有多少个等于目标”。这两个问题的答案就是 lower_bound 和 upper_bound。

• lower_bound(nums, target)：第一个大于等于target 的位置。
• upper_bound(nums, target)：第一个严格大于target 的位置。

def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 # mid 太小，答案在右边 else: right = mid # mid 可能是答案，保留 return left def upper_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] <= target: left = mid + 1 # 注意和上面只差一个等号 else: right = mid return left

这两段代码只差一处：一个比较是<，一个是<=。含义就是“边界向哪边靠”。有了这两个函数，很多问题一行就解决了：

def count_occurrences(nums, target): return upper_bound(nums, target) - lower_bound(nums, target) def first_position(nums, target): i = lower_bound(nums, target) return i if i < len(nums) and nums[i] == target else -1 def last_position(nums, target): i = upper_bound(nums, target) - 1 return i if i >= 0 and nums[i] == target else -1

Python 标准库里的bisect模块就是这两个函数：bisect.bisect_left对应 lower_bound，bisect.bisect_right对应 upper_bound。实际项目里请优先用bisect，它是 C 实现的，速度快，而且不会有边界 bug。手写是学习手段，生产代码里手写 lower_bound 属于给自己找麻烦——我参与过的项目里，自己实现二分边界查找的代码在多次重构后出问题的概率明显高于直接调库。

4.2 二分答案：把“查找”变成“判断”

二分最强大的用法不是查数组，而是查答案空间。套路是：先确定答案一定落在某个区间[lo, hi]里，然后写一个feasible(x)判断“答案等于 x 是否可行”，只要这个判断函数关于 x 是单调的（x 越大越可行，或越不可行），就可以用二分把最优答案逼出来。

举个具体例子：把一个数组按顺序切成 m 段，让各段和的最大值最小。

def split_array(nums, m): def feasible(limit): """每段和不超过 limit 时，最少需要切几段？""" count, current = 1, 0 for x in nums: if current + x > limit: count += 1 current = x if count > m: return False else: current += x return True left, right = max(nums), sum(nums) # 答案区间：最大单元素 ~ 全部加起来 while left < right: mid = left + (right - left) // 2 if feasible(mid): right = mid # mid 可行，试着更小 else: left = mid + 1 # mid 不可行，必须更大 return left

这里最关键的一步是确定答案区间的左右端点。左端点取max(nums)，因为任何一段的和都不可能小于最大的单个元素；右端点取sum(nums)，因为一段都不切也满足条件（前提是 m >= 1）。这两个端点选错了，二分就找不到正确答案。我在写这类题的时候，第一件事永远是把端点和可行性的单调方向写在一张纸上，然后再动手码字。

4.3 旋转数组查找与浮点二分

有序数组被旋转过一段（比如[4,5,6,7,0,1,2]），还能不能二分？能，思路是“每次判断哪一半是有序的，再判断目标在不在这一半里”。

def search_rotated(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[left] <= nums[mid]: # 左半段有序 if nums[left] <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: # 右半段有序 if nums[mid] < target <= nums[right]: left = mid + 1 else: right = mid - 1 return -1

另一个常见变体是浮点数二分，比如求平方根。这里的坑和整数完全相反：浮点二分不能用left <= right做终止条件，因为浮点数精度有限，区间可能永远缩不到一个点。正确做法是固定迭代次数，或者用区间宽度小于 eps 作为退出条件。

def sqrt_float(x, iterations=100): if x < 0: raise ValueError("负数没有实数平方根") left, right = 0.0, max(1.0, x) for _ in range(iterations): # 固定 100 次，精度远超 double 极限 mid = (left + right) / 2 if mid * mid < x: left = mid else: right = mid return (left + right) / 2

固定迭代次数比 eps 判断更稳，因为 100 次二分能把初始区间缩小 2^100 倍，早就超过双精度浮点的表示精度了，再多迭代也是浪费。这个“用次数控制而不是用精度控制”的技巧，在数值计算里是很通用的一条经验。

4.4 变种写法的统一心法

上面这些变种看起来五花八门，其实可以收敛成一套心法，我总结成三句话：

按这套心法写，lower_bound、upper_bound、找插入位置、找第一个错误版本这些题，代码结构几乎一模一样，只改中间那个判断条件。这也是我推荐新手先死磕lower_bound的原因——它不是一道题，它是这一类题的地基。

5. 三种方法的实测对照与选型判断

5.1 跑个基准测试，用数据说话

理论复杂度是一回事，实际耗时是另一回事。下面这段脚本可以直接跑，对比四种写法（顺序、迭代二分、递归二分、bisect）在不同数据规模下的表现。

import bisect import random import time def sequential_search(arr, target): for i, v in enumerate(arr): if v == target: return i return -1 def binary_search_closed(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: right = mid - 1 return -1 def binary_search_recursive(nums, target, left=None, right=None): if left is None: left, right = 0, len(nums) - 1 if left > right: return -1 mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[mid] < target: return binary_search_recursive(nums, target, mid + 1, right) return binary_search_recursive(nums, target, left, mid - 1) def bench(n, rounds=500): data = sorted(random.sample(range(n * 10), n)) targets = [random.randrange(n * 10) for _ in range(rounds)] def timeit(fn, *extra): t0 = time.perf_counter() for t in targets: fn(data, t, *extra) return time.perf_counter() - t0 return { "顺序": timeit(sequential_search), "迭代二分": timeit(binary_search_closed), "递归二分": timeit(binary_search_recursive), "bisect": timeit(bisect.bisect_left), } for n in (100, 1_000, 10_000, 100_000, 1_000_000): r = bench(n) print(f"n={n:>8} " + " ".join(f"{k}={v*1000:.2f}ms" for k, v in r.items()))

我这边跑出来的趋势大致是这样的（具体数值跟机器强相关，看相对量级就行）：

这里有个很值得注意的现象：在 n = 100 这个量级，顺序查找和迭代二分的差距基本在噪声范围内，甚至因为顺序查找的循环体更简单（没有除法、没有额外变量），有时候还略快一点。这印证了前面说的那句：小数据量下不要迷信二分。

到 n = 1,000,000 时，差距就拉开了：顺序查找要扫几十万次才能命中，二分只需要 20 次比较，差了三四个数量级。而递归二分稳定地比迭代二分慢 2 到 3 倍，这个差距纯粹来自函数调用开销——因为在 Python 里，一次函数调用的成本大约是一次简单循环迭代的十几倍。

5.2 选型的三条经验规则

跑完测试，我把选型规则整理成三句话，日常够用了。

第一条：数据无序且只查一次，用顺序查找。这时候排序的 O(n log n) 是纯亏，尤其是 n 小的时候。只有当查询次数乘上 log n 之后能覆盖排序成本，预处理才有意义。粗略估算是：查询次数超过 log2(n) 的几倍之后，排序就值了。

第二条：数据有序且查询频繁，用二分，且优先用标准库。Python 用bisect，C++ 用std::lower_bound，Java 用Arrays.binarySearch。库实现经过大量测试，不会有边界 bug，而且通常有底层优化。手写只在你需要自定义比较逻辑、或者需要同时返回多个信息（比如命中位置和比较次数）时才考虑。

第三条：需要找边界、找插入位置、或者答案是数值区间，用二分模板而不是普通二分。普通二分只会返回“某一个命中位置”，一旦有重复元素，结果就不确定。这种情况下必须换成lower_bound或upper_bound。

5.3 我在实战里攒下的几条调试经验

最后分享几条我认为最值钱的东西，都是踩过坑之后才记住的。

第一，二分写完先别急着测正确用例，先测空数组和单元素数组。这两个用例能干掉一半以上的越界和死循环问题。我的习惯是写完立刻跑[]、[1]、[1,1]三个输入，通过了再看业务逻辑。

第二，用暴力对拍验证。写二分的时候，同时写一个顺序查找版本，然后随机生成几千组小数组（长度 0 到 10，元素范围 0 到 5，允许重复），逐个比对两个函数的结果。这个技巧能抓出所有边界 bug，而且写起来只要十行代码。我现在写任何带下标的算法都用这一招，比人工构造用例可靠得多。

import random def fuzz_check(binary_fn, rounds=5000): for _ in range(rounds): n = random.randint(0, 10) nums = sorted(random.randint(0, 5) for _ in range(n)) target = random.randint(-1, 6) expected = nums.index(target) if target in nums else -1 got = binary_fn(nums, target) # 有重复元素时只要求"命中且值正确"，不要求下标一致 assert (got == expected) or (got != -1 and nums[got] == target), \ f"不一致：nums={nums}, target={target}, got={got}, expected={expected}"

第三，不要相信“我记得是这样写”的二分。二分是一种肌肉记忆型的代码，隔三个月不写，<=和<就会记混。我自己是把一个标准的lower_bound模板存在编辑器片段里，需要的时候直接展开，只改中间那个判断条件。这比每次凭记忆重写快得多，也稳得多。

第四，遇到“答案是一个数值区间”的问题，先问自己判断函数单调不单调。只要单调，八成能二分。这个思路的适用范围远超“在数组里找数”，包括资源分配、负载均衡、阈值调优这类看起来完全不像查找的问题。我见过太多人一上来就写暴力枚举或者动态规划，其实一个二分加一个判断函数就解决了。

第五，注意浮点数比较。只要出现浮点二分，就不要用==判断相等，也不要指望区间能收缩到一个点。固定迭代次数是最稳的选择，宁可多算十次也不要写出一个因为精度问题偶尔死循环的代码。

提示：如果你在用 Python 并且只需要“在有序序列里插入一个值并保持有序”，直接用bisect.insort比“二分找位置 +list.insert”更省事。list.insert本身是 O(n) 的，所以整体复杂度还是 O(n)，这一点别被二分的 O(log n) 迷惑了——查找是 log n，插入不是。

我在实际项目里的体会是，这三种查找方法的价值不在于性能数字，而在于它们代表了三种不同的思维：顺序查找是“老老实实把可能性走一遍”，二分查找是“利用结构信息排除一半”，二分答案是把“求解”转化成“判断”。前两种是工具，第三种是思路。工具用错了顶多慢一点，思路用错了就会在明明有 O(log n) 解法的地方写出 O(n²)。至于递归还是迭代，那真的只是写法问题——把区间定清楚，把收缩规则写对，剩下的选择看团队习惯就好。