Python implementation of linear and binary search for elements in a list
发布时间
阅读量：
阅读量
python实现二分查找的两种方式
二分查找：时间复杂度为O(logn)
采用该方式的前提条件是数据结构需按照关键字的大小顺序进行排列，并且必须为顺序存储形式。
在本例中，所采用的为按升序排列的数组结构
class BinarySearch:
# 非递归
def binarysearch1(self, arr, x, l, r):
# 循环直到找到或是确认没有为止
while True:
# 右边界大于等于左边界时执行
if r >= l:
# 索引中间值，需要保证为int
mid = int(l + (r - l) / 2)
# 若刚好等于中间值
if x == arr[mid]:
return mid
# 落在右边
elif x > arr[mid]:
l = mid + 1
# 落在左边
else:全部评论 (0)
还没有任何评论哟~