算法-二分法查找

时间:2021-06-15 22:10:30

前提条件:列表必须有序,列表从小到大。

二分法原理:找到列表的中间值,比较这个值与要查找的值的大小,若比这个值大,则把区间缩小到左边,反之右边。然后继续相同的步骤,直到找到。

二分法时间复杂度:O(logn)


def bin_search(data,val):
left = 0
right = len(data) - 1
while left <= right:
mid = (left + right) // 2
if data[mid] < val:
left = mid + 1
elif data[mid] > val:
right = mid -1
elif data[mid] == val:
return mid