Python 二分查找与 bisect 模块_程序人生

Python 二分查找与 bisect 模块

admin

2023-07-31 00:47:26

0次

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

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

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

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

12345678910111213141516171819202122

def binary_search_recursion(lst, value, low, high): if high < low: return None mid = (low + high) / 2 if lst[mid] > value: return binary_search_recursion(lst, value, low, mid–1) elif lst[mid] < value: return binary_search_recursion(lst, value, mid+1, high) else: return mid def binary_search_loop(lst,value): low, high = 0, len(lst)–1 while low <= high: mid = (low + high) / 2 if lst[mid] < value: low = mid + 1 elif lst[mid] > value: high = mid – 1 else: return mid return None

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

1234567891011121314151617

if __name__ == \”__main__\”: import random lst = [random.randint(0, 10000) for _ in xrange(100000)] lst.sort() def test_recursion(): binary_search_recursion(lst, 999, 0, len(lst)–1) def test_loop(): binary_search_loop(lst, 999) import timeit t1 = timeit.Timer(\”test_recursion()\”, setup=\”from __main__ import test_recursion\”) t2 = timeit.Timer(\”test_loop()\”, setup=\”from __main__ import test_loop\”) print \”Recursion:\”, t1.timeit() print \”Loop:\”, t2.timeit()

执行结果如下：

12	Recursion: 3.12596702576Loop: 2.08254289627

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

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

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

1234567891011121314

import bisectimport random random.seed(l>

1.从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

2.如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

3.如果在某一步骤数组为空，则代表找不到。

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

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

12345678910111213141516171819202122

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

1234567891011121314151617

执行结果如下：

12	Recursion: 3.12596702576Loop: 2.08254289627

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

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

1234567891011121314

import bisectimport random

上一篇：Python 进阶_生成器 & 生成器表达式

下一篇：Python源码分析-PyDictObject

Python 二分查找与 bisect 模块

相关内容

热门资讯