一、迭代
def binary_search(key, ls):
left = 0
right = len(ls) -1
while left <= right:
mid = (left + right) // 2
if key == ls[mid]:
return mid
elif key < ls[mid]:
right = mid - 1
elif key > ls[mid]:
left = mid + 1
return -1
二、递归
def binary_search(ls, low, high, key):
if low > high:
return -1
else:
mid = (low+high)//2
if key == ls[mid]:
return mid
elif key > ls[mid]:
return binary_search(ls, mid+1, high, key)
else:
return binary_search(ls, low, mid-1, key)
网友评论