二分法查找及其python实现案例 python实现二分法查找

文章插图
在计算机科学中。二分搜索（英语：binary search）。也称折半搜索（英语：half-interval search）[1]、对数搜索（英语：logarithmic search）[2] 。是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始。如果中间元素正好是要查找的元素。则搜索过程结束；如果某一特定元素大于或者小于中间元素。则在数组大于或小于中间元素的那一半中查找。而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空。则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

文章插图
输出结果是：

文章插图
Bisect模块提供的函数有：(1)查找bisect.bisect_left(a,x, lo=0, hi=len(a)) :
查找在有序列表a中插入x的index 。lo和hi用于指定列表的区间。默认是使用整个列表。
bisect.bisect_right(a,x, lo=0, hi=len(a))
bisect.bisect(a, x,lo=0, hi=len(a))
这2个和bisect_left差不多。但如果x已经存在。在其右边插入。
（2）插入bisect.insort_left(a,x, lo=0, hi=len(a))
在有序列表a中插入x 。如果x已经存在。在其左边插入。返回值为index 。和a.insert(bisect.bisect_left(a,x, lo, hi), x) 的效果相同。
bisect.insort_right(a,x, lo=0, hi=len(a))
bisect.insort(a, x,lo=0, hi=len(a))
和insort_left差不多。但如果x已经存在。在其右边插入。
【二分法查找及其python实现案例 python实现二分法查找】可以函数可以分2类。bisect* 。用于查找index 。Insort*用于实际插入。默认重复时从右边插入。实际常用的估计是insort 。