# 递归版本
def binary_search(l, item):
length = len(l)
if length == 0:
return False
mid = length//2
if item == l[mid]:
return True
elif item < l[mid]:
return binary_search(l[0:mid], item)
elif item > l[mid]:
return binary_search(l[mid+1:], item)
print(binary_search([1,2,3,4,5,6,7], 7))
# 非递归版本
def binary_search(l, item):
start = 0
end = len(l)-1
while start <= end:
mid = (start + end) // 2
if item == l[mid]:
return True
elif item < l[mid]:
end = mid - 1
else:
start = mid + 1
return False
# 需求：返回找到的第一个数据的下标
def binary_search(l, item):
start = 0
end = len(l)-1
while start <= end:
mid = (start + end) // 2
if item == l[mid]:
if mid == 0 or item == l[mid-1]:
return mid
else:
end = mid - 1
elif item < l[mid]:
end = mid - 1
else:
start = mid + 1
return -1
