Python中二分查找函数与list.index()的效率对比及适用场景

我结合你的测试数据，来逐一拆解这些问题：

1. list.index()采用的查找算法 #

Python内置的list.index()实现的是线性查找（顺序查找）——它会从列表的第一个元素开始逐个比对，直到找到目标元素或者遍历完整个列表。这刚好能解释你的测试结果：查找位于列表后半段的767376时，list.index()耗时是二分查找的4倍左右，因为它需要遍历近一半的元素；而查找22500（即150²，位于列表前1.5%的位置）时，两者耗时接近，因为线性查找很快就定位到了目标。

2. 何时选择list.index()或自定义二分查找？ #

优先用list.index()的场景 #

• 列表无序：二分查找的核心前提是列表有序，如果你的列表没法保证有序，要么直接用list.index()，要么先排序再二分——但排序本身的时间成本（O(n log n)）可能比单次线性查找更高，得不偿失。
• 数据量很小：比如列表只有几十上百个元素时，线性查找的常数项优势（不需要计算中间索引、边界判断等额外逻辑）会让它的实际耗时和二分查找差距不大，甚至因为list.index()是C实现的高度优化代码，速度还能更快。而且用内置方法代码更简洁，不用自己维护二分查找的逻辑。
• 需要定位第一个匹配项：如果列表里有重复元素，list.index()会返回第一个出现的位置；而你的二分查找可能返回任意一个匹配的位置（取决于中间值的命中情况），如果需要第一个匹配项，线性查找更直接，不需要额外修改二分查找的逻辑。

优先用自定义二分查找的场景 #

• 有序列表+数据量大：像你测试的10000个元素的有序列表，查找后半段元素时优势已经很明显；如果是十万、百万级的有序列表，二分查找的O(log n)复杂度会把线性查找的O(n)甩得很远，累计查找次数越多，优势越显著。
• 频繁查找同一个有序列表：如果你的程序要多次对同一个有序列表执行查找操作，二分查找的累计时间节省会非常可观。

3. 影响两者效率的核心因素 #

• 列表的有序性：这是二分查找的硬前提，无序列表根本没法用二分查找，只能选list.index()。
• 目标元素的位置：
  • 对list.index()来说，目标越靠前，耗时越少；越靠后，耗时越多，最坏情况是目标不存在，需要遍历整个列表。
  • 对二分查找来说，不管目标在哪个位置，查找次数都是O(log n)级别的，位置对耗时的影响微乎其微。
• 列表规模：
  • 小规模列表（n<100）：两者耗时差异极小，list.index()甚至可能更快，因为内置实现的常数开销更低。
  • 大规模列表（n>1000）：二分查找的复杂度优势会彻底显现，数据量越大，差距越明显。
• 重复元素的存在：如果列表有大量重复元素，list.index()天然返回第一个匹配项；而二分查找需要额外逻辑才能定位到第一个/最后一个匹配项，这时候如果需求是特定位置的匹配，要结合需求来选择。

内容的提问来源于stack exchange，提问作者Jonas Palačionis