代码语言：javascript复制
# -*- coding: utf-8 -*-
"""
@author: sato
@file: binary_search.py
@time: 2019-09-03 15:21
"""
def binary_search(array, key):
"""二分查找非递归"""
if len(array) <= 1:
if array[0] != key:
return
start = 0
end = len(array) - 1
while start <= end:
mid = (end start) // 2
if key < array[mid]:
end = mid - 1
elif key > array[mid]:
start = mid 1
else:
return True
def binary_search(a, b):
"""非递归"""
min = 0
max = len(a) - 1
if b in a:
while True:
centre = int((max min) / 2)
if a[centre] > b:
max = centre - 1
elif a[centre] < b:
min = centre 1
elif a[centre] == b:
return centre
else:
return 'b in not in a'
def binary_search_reduce(array, key):
"""二分查找，递归实现版本"""
if len(array) == 0:
return False
mid = len(array) // 2
if array[mid] == key:
return True
elif key < array[mid]:
return binary_search_reduce(array[:mid], key)
else:
return binary_search_reduce(array[mid 1:], key)
if __name__ == '__main__':
# 二分查找的最优时间复杂度为O（1），最坏时间复杂度为O（log n）
# 递归空间复杂度是：O(N) 非递归: O(1)
# 使用场景： 在有序数组中寻找指定元素
sorted_list = [1, 4, 5, 7, 8, 9, 10, 13, 15, 17, 19, 23, 35]
assert binary_search(sorted_list, 1)
assert binary_search(sorted_list, 10)
assert binary_search(sorted_list, 35)
assert binary_search_reduce(sorted_list, 1)
assert binary_search_reduce(sorted_list, 13)
assert binary_search_reduce(sorted_list, 35)
