二分查找边界条件详解：从手写实现到Python bisect实战

二分查找不是一个“会不会背模板”的问题，而是一个“边界条件写不写得对”的问题。很多初学者第一次写二分查找都能写出大概逻辑，但一运行就出现死循环、漏掉元素、下标越界，或者面对“查找第一个等于目标值的位置”“查找最后一个小于目标值的位置”这类变体时直接懵掉。这篇文章不绕弯子，直接讲清楚二分查找的原理、两种最常见的区间写法、各种变体怎么写，以及 Python 内置的bisect模块在工程里怎么用。

文中所有代码都基于 Python 3，不需要额外安装任何第三方库，复制到本地就能运行。内容覆盖基础实现、边界写法、性能对比、LeetCode 经典例题、常见报错排查，读完可以直接把模板沉淀到自己的代码库里。

1. 二分查找核心能力速览

先把二分查找的核心信息拉出来，方便快速判断它适合解决什么问题。

二分查找的价值不在于“在一个数组里找一个数”这个场景有多复杂，而在于它是很多高级算法的基础。比如旋转排序数组的最小值、寻找峰值、求平方根、有序矩阵搜索，底层都是二分思想。理解二分查找的边界处理，后面这些题都会顺利很多。

2. 二分查找的适用场景与使用边界

2.1 什么时候应该用二分查找

二分查找解决的核心问题只有一个：在有序序列中快速定位目标或目标区间。具体来说，以下几类场景非常典型。

第一，静态有序数据的高频搜索。比如一个按 ID 升序排列的用户列表，需要频繁判断某个 ID 是否存在；一个按时间排序的日志数组，需要快速定位某条时间戳的位置。数据只构建一次，但查询很多次，这时二分查找比逐一遍历划算得多。

第二，需要“找到插入位置”的场景。比如维护一个有序列表，每次插入新元素都要保持顺序，可以直接用二分查找确定索引位置，再执行插入操作。bisect模块正是为这种场景设计的。

第三，算法题中二分答案的套路。很多最优化问题的思路是：枚举一个答案，判断它是否可行，然后在这个答案的取值范围内二分。典型例子包括“在 D 天内送达包裹的能力”“分割数组的最大值”这类题目。这种场景不是直接搜数组元素，而是把二分思想套在答案值域上。

2.2 什么时候不应该用二分查找

不是所有“找元素”的问题都适合二分查找。

如果数据本身无序，二分查找不能用。必须先排序，而排序的时间复杂度是 O(n log n)，如果整个任务只搜索一次，那不如直接 O(n) 线性扫一遍，尤其是数据量不大的时候。

如果是链表结构，即使链表有序，也不适合二分查找。链表不支持 O(1) 随机访问，取中间元素需要从头遍历，整体复杂度退化为 O(n log n)，还不如直接遍历。

如果数据频繁插入和删除，维护有序数组的成本很高。每次插入都要移动元素，这时应该考虑平衡二叉树、跳表、堆等动态数据结构，而不是用二分查找搭配数组。

2.3 使用边界与合规提醒

二分查找本身没有任何安全和版权风险，但如果在实际业务中使用，要注意数据来源的合法性问题。比如对用户数据、日志数据、爬虫采集到的数据做检索时，必须确保数据获取方式符合平台规则和相关法律法规。涉及个人信息时，要先完成脱敏处理。算法只是工具，数据处理流程里的合规问题同样重要。

3. 环境准备与前置条件

二分查找对运行环境的要求极低，几乎任何能跑 Python 的环境都可以。

3.1 操作系统与 Python 版本

• Windows / macOS / Linux 均可。
• Python 3.6 及以上版本即可，建议使用 Python 3.8+。
• 不需要安装第三方库，标准库bisect已经覆盖工程场景。

3.2 运行方式

最简单的验证方式是准备一个.py文件，然后在终端执行：

python binary_search_demo.py

如果是刚接触 Python，还没装好环境，可以参考以下步骤快速搭建。

3.3 Python 安装检查

在终端执行：

python --version

如果提示command not found，说明 Python 还没加入环境变量。Windows 用户在安装 Python 时勾选 "Add Python to PATH"，重新打开终端后再检查。macOS 用户可以用python3 --version检查。Linux 用户一般自带 Python 3，也可以直接执行python3 --version。

3.4 编辑器选择

日常练习随便用，PyCharm、VS Code、IDLE、Jupyter Notebook 都可以。如果主要在本地写算法题，推荐 VS Code + Python 插件，调试时可以直接查看变量变化，对理解边界条件很有帮助。

建议先创建一个专门存放算法练习的目录，例如：

mkdir -p ~/algorithm_practice cd ~/algorithm_practice

4. 二分查找基础实现

二分查找的写法可以有很多种，但核心就一句话：维护一个左闭右闭或左闭右开的搜索区间，每次取中间元素，与目标值比较，得到结果后缩小区间。两种区间写法对应不同的循环条件、区间更新方式，很多人写错就是两种写法混用了。

4.1 左闭右闭写法

左闭右闭写法的区间是[left, right]，left和right指向的元素都在搜索范围内，因此循环条件是while left <= right。当left > right时，搜索区间为空。

def binary_search(nums: list[int], target: int) -> int: 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

几个关键细节：

• mid = left + (right - left) // 2而不是(left + right) // 2，前者能避免极端情况下left + right整数溢出（Python 里这个顾虑不大，但是好习惯）。
• 当nums[mid] < target时，说明中间值太小，目标值一定在右半区，所以left = mid + 1。
• 当nums[mid] > target时，说明中间值太大，目标值一定在左半区，所以right = mid - 1。
• 循环结束后返回-1，表示没有找到。

测试一下：

nums = [1, 3, 5, 7, 9, 11, 13] print(binary_search(nums, 7)) # 预期输出 3 print(binary_search(nums, 4)) # 预期输出 -1

4.2 左闭右开写法

左闭右开写法的区间是[left, right)，right指向的元素不在搜索范围内，因此循环条件是while left < right。当left == right时，区间已经为空。

def binary_search_right_open(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

这里最容易写错的就是right = mid。因为区间是左闭右开，mid已经不可能是目标值时，right应该收缩到mid，保证[left, right)仍然覆盖真正的搜索区间。

4.3 递归写法

递归写法在思路上更直观，但实际工程中不建议频繁使用，因为栈深度受限制。数据量很大时可能出现递归深度超出 Python 默认限制的问题。这里给出一个参考版本：

def binary_search_recursive(nums: list[int], target: int, left: int, right: int) -> int: if left > right: return -1 mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: return binary_search_recursive(nums, target, mid + 1, right) else: return binary_search_recursive(nums, target, left, mid - 1)

4.4 手写二分还是用 bisect

如果只是做算法练习，手写一遍非常有必要，能帮助你理解边界。但在生产代码里，更推荐直接用 Python 标准库的bisect。原因很简单：标准库实现经过大量测试，边界情况处理得比较稳，且代码更易读。后面的章节会专门讲bisect的用法。

5. 二分查找变体：边界查找

基础版二分查找能解决“找是否存在某个值”的问题，但真实业务里更常见的是“找第一个大于等于目标值的位置”“找最后一个等于目标值的位置”这类边界问题。这类问题最容易出错，也是面试高频考点。

5.1 查找第一个等于目标值的位置

如果有重复元素，基础版二分查找返回的可能是任意一个等于目标值的位置。要找到“第一个”，需要在nums[mid] == target时，不直接返回，而是继续向左搜索。

def find_first_equal(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: result = mid right = mid - 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return result

执行逻辑是：找到目标值时记录当前索引，然后把right收缩到mid - 1，继续看看左边还有没有。循环结束后，result就是最左边的目标值索引。

5.2 查找最后一个等于目标值的位置

方法与上面对称，找到目标值时记录索引，然后继续向右搜索。

def find_last_equal(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: result = mid left = mid + 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return result

5.3 查找第一个大于等于目标值的位置

这个变体在工程里非常常用，比如要在有序列表中插入一个元素，使列表仍然有序，就应该用这个逻辑。bisect_left的底层原理就是这个。

def find_first_ge(nums: list[int], target: int) -> int: 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

返回的是第一个不小于target的索引。如果所有元素都小于target，返回len(nums)，表示应该插入在末尾。

5.4 查找最后一个小于等于目标值的位置

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

这几个变体互相之间只差一两个条件。建议把这四段代码手动敲一遍，然后放到本地跑几个用例，重点观察循环结束后的索引位置。

6. 使用 Python 内置 bisect 模块

手写二分是理解原理，工程中直接用bisect才是高效做法。bisect是 Python 标准库，不需要安装，导入就能用。

import bisect

6.1 核心函数

bisect_left和bisect_right的区别在有重复元素时最明显。

import bisect nums = [1, 3, 3, 3, 5, 7, 9] print(bisect.bisect_left(nums, 3)) # 输出 1 print(bisect.bisect_right(nums, 3)) # 输出 4

bisect_left(nums, 3)返回第一个值为 3 的位置，索引是 1。bisect_right(nums, 3)返回最后一个值为 3 的位置的下一个位置，索引是 4。用这两个函数可以很方便地完成很多操作。

6.2 用 bisect 判断元素是否存在

有重复元素时，判断元素是否存在不能用bisect_left直接判断索引是否命中，因为bisect_left总是返回一个插入位置。标准做法是：

def contains(nums: list[int], target: int) -> bool: pos = bisect.bisect_left(nums, target) return pos < len(nums) and nums[pos] == target

6.3 用 bisect 统计重复元素个数

def count_occurrences(nums: list[int], target: int) -> int: left = bisect.bisect_left(nums, target) right = bisect.bisect_right(nums, target) return right - left

6.4 用 bisect 维护有序插入

import bisect sorted_list = [1, 3, 5, 7, 9] bisect.insort(sorted_list, 6) print(sorted_list) # 输出 [1, 3, 5, 6, 7, 9]

insort的底层就是先找出插入位置，再执行列表插入操作。注意list.insert是 O(n) 操作，所以如果插入非常频繁且数据量很大，bisect.insort并不适合作为高性能方案，这时应该考虑数据结构层面的优化。

7. 二分查找性能测试与对比方法

二分查找的优势是 O(log n)。为了直观感受，可以写一个简单脚本，对比线性查找和二分查找在相同数据上的比较次数。

7.1 统计比较次数

def linear_search_count(nums: list[int], target: int) -> int: count = 0 for num in nums: count += 1 if num == target: break return count def binary_search_count(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 count = 0 while left <= right: count += 1 mid = left + (right - left) // 2 if nums[mid] == target: break elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return count nums = list(range(1000000)) print(linear_search_count(nums, 999999)) # 线性查找需要 1000000 次比较 print(binary_search_count(nums, 999999)) # 二分查找通常只需要约 20 次比较

这段代码不会影响性能，只是一个观察方式。真正工程里评估性能，应该用timeit模块对多次调用求平均：

import timeit import bisect nums = list(range(1000000)) target = 999999 linear_time = timeit.timeit(lambda: target in nums, number=100) binary_time = timeit.timeit(lambda: bisect.bisect_left(nums, target), number=100) print(f"linear: {linear_time:.4f}s") print(f"binary: {binary_time:.4f}s")

不同机器上运行结果会有差异，但整体趋势很明确：数据量越大，二分查找的优势越明显。

7.2 为什么 mid 要写成 left + (right - left) // 2

很多讲解直接给出这个写法，但没解释原因。其实核心原因是防溢出。在 C++ 或 Java 中，left + right可能超过整数范围，导致计算错误。Python 的整数可以无限大，所以这个问题不明显，但保持这个写法能保证算法代码在不同语言间迁移时仍然正确。

7.3 二分查找对数据规模的要求

二分查找比较次数约为log2(n)次。数据量从 1000 增长到 100 万，二分查找的比较次数只从约 10 次增长到约 20 次。这就是 O(log n) 的含义。理解这个增长曲线，比单纯记住复杂度公式更有用。

8. 二分查找经典问题与解题思路

理解了基础和边界写法后，直接刷一遍 LeetCode 的高频题目，效果比看十篇教程更好。下面列出的题目覆盖了二分查找最常见的几种考法。

8.1 LeetCode 704 二分查找

最基础的题目，直接套左闭右闭模板即可。这道题的意义是检验你能不能一次写对循环条件。

def search(nums: list[int], target: int) -> int: 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

8.2 LeetCode 35 搜索插入位置

要求返回目标值在有序数组中的索引，如果不存在则返回应该插入的位置。这题其实就是bisect_left的逻辑。

def search_insert(nums: list[int], target: int) -> int: 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

8.3 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

这道题是变体的直接应用，分别找第一个等于 target 和最后一个等于 target 的索引。

def search_range(nums: list[int], target: int) -> list[int]: def find_left(): left, right = 0, len(nums) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: result = mid right = mid - 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return result def find_right(): left, right = 0, len(nums) - 1 result = -1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: result = mid left = mid + 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return result return [find_left(), find_right()]

也可以用bisect_left和bisect_right简写，但面试时建议先手写一遍，再提标准库方案。

8.4 LeetCode 278 第一个错误的版本

这题的难点在于理解“版本数组”实际上是[False, False, ..., True, True]这样的结构，要找第一个 True。直接用左闭右开模板。

def first_bad_version(n: int) -> int: left, right = 1, n while left < right: mid = left + (right - left) // 2 if is_bad_version(mid): right = mid else: left = mid + 1 return left

8.5 LeetCode 153 寻找旋转排序数组中的最小值

旋转数组的特点是数组原本有序，但在某个点旋转了。最小值左边的元素都大于右边。可以二分查找最小值位置。

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

8.6 LeetCode 162 寻找峰值

峰值元素是大于左右相邻元素的元素。由于相邻元素不相等，可以二分查找。

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

8.7 二分答案思想

有些问题不是直接在一个数组里二分，而是在答案的取值范围上二分。比如：

• 给定一个数组和一个整数 k，问能否在 k 次操作内让数组中的最大值最小。
• 给定一个正整数 x，求 x 的平方根整数部分。

这类题目的套路是先确定答案的上下界，然后写一个check(mid)函数判断当前答案是否可行，再根据check的结果调整区间。

def my_sqrt(x: int) -> int: left, right = 0, x while left <= right: mid = left + (right - left) // 2 if mid * mid <= x: left = mid + 1 else: right = mid - 1 return right

这道题把所有可能的整数根当作搜索空间，对每个 mid 判断mid * mid是否小于等于 x，最后返回最大的满足条件的结果。

二分答案思想的应用范围比“在数组中查找元素”广得多。遇到“最大值最小”“最小值最大”这类说法时，第一反应就应该是二分答案。

9. 二分查找常见问题与排查方法

写二分查找时常见的坑其实就集中在几个位置。下面把这些坑统一列成排查表。

9.1 空数组处理

基础版二分查找里，len(nums) - 1在空数组时会得到-1，此时left=0, right=-1，循环条件不成立，直接返回-1，逻辑没问题。但如果你写的是左闭右开写法，right = len(nums)，空数组时right = 0，left < right不成立，也会返回-1。所以大多数模板对空数组是天然安全的。不过为了可读性，建议在函数入口加一行：

if not nums: return -1

9.2 打印调试法

刚开始学二分查找时，如果死活找不到 bug，不要盯着代码空想。直接在循环里打印中间变量。

while left <= right: mid = left + (right - left) // 2 print(f"left={left}, right={right}, mid={mid}, nums[mid]={nums[mid]}")

观察每一轮区间是怎么收缩的，很快就能定位是条件写反了，还是区间收窄方式错了。

10. 最佳实践与代码模板

10.1 标准左闭右闭模板

def binary_search(nums: list[int], target: int) -> int: if not nums: return -1 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

10.2 标准左闭右开模板

def binary_search(nums: list[int], target: int) -> int: if not nums: return -1 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

10.3 工程建议

• 生产环境优先用bisect，不要自己造轮子。只有在算法面试或特殊需求下才手写。
• 手写时选定一种区间开闭方式，整个函数保持统一，不要混用。
• 每次写完测试三个边界用例：空数组、单元素数组、目标值在数组首位或末位。
• 把常用变体封装成函数，放在自己的工具模块里，例如“第一个大于等于”“最后一个小于等于”。
• 面试时先和面试官确认区间写法，再用模板写代码，最后口头解释边界条件，会让表达更清楚。

10.4 一个可复用的工具库示例

import bisect def first_ge(nums: list[int], target: int) -> int: return bisect.bisect_left(nums, target) def first_gt(nums: list[int], target: int) -> int: return bisect.bisect_right(nums, target) def last_le(nums: list[int], target: int) -> int: pos = bisect.bisect_right(nums, target) return pos - 1 if pos > 0 else -1 def last_lt(nums: list[int], target: int) -> int: pos = bisect.bisect_left(nums, target) return pos - 1 if pos > 0 else -1

这几个函数本质上都是bisect_left和bisect_right的排列组合，理解了之后可以直接组合出各种边界查询。

11. 总结与下一步

二分查找最值得花时间的地方，不是背模板，而是理解区间开闭和边界条件。建议你先手动敲一遍左闭右闭和左闭右开两个版本，然后跑一下 704、35、34、278、153、162 这几道 LeetCode 题，看看自己会在哪里出错，再回来看本文第 5 节和第 9 节，定位问题会很快。

最容易踩的坑就是混用区间写法：循环条件用的是<=，更新边界时却用了right = mid，或者反过来。记住一个原则——先确定区间类型，再写循环条件和更新语句，全程保持一致。

下一步可以往两个方向继续深入：一是把二分查找和三分查找、二分答案放到一起对比学习，理解二分思想在更多问题中的应用；二是结合bisect标准库，在自己的 Python 项目中应用有序列表的批量插入和区间查询能力。把二分查找从“会背模板”变成“能灵活变体”，很多算法题的思路会顺很多。