Python 的列表（list）内部实现是一个数组，也就是一个线性表。在列表中查找元素可以使用 list.index() 方法，其时间复杂度为O(n)。对于大数据量，则可以用二分查找进行优化。二分查找要求对象必须有序，其基本原理如下：

• 1.从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
• 2.如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
• 3.如果在某一步骤数组为空，则代表找不到。

二分查找也成为折半查找，算法每一次比较都使搜索范围缩小一半， 其时间复杂度为 O(logn)。

我们分别用递归和循环来实现二分查找：

接着对这两种实现进行一下性能测试：

执行结果如下：

可以看出循环方式比递归效率高。

Python 有一个 bisect 模块，用于维护有序列表。bisect 模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用 sort 的方式维护有序列表。

下面是一个简单的使用示例：