实现思路
- 将数组的中间元素array_to_search[middle]与待查找数number进行比较，如果相等，则成功找到，结束；
- 若array_to_search[middle] > number，则number只可能出现在array_to_search的前半段，放弃对后半段的查找，查找规模减半，回到步骤1；
- 若array_to_search[middle] < number，则number只可能出现在array_to_search的后半段，放弃对前半段的查找，查找规模减半，回到步骤1；
- 若查找规模 = 1时仍然没有查找到number，则待查找数组中没有number，结束。
两个例子
查找成功
middle = (0 + 7) // 2 = 3，array_to_search[middle ] = 16， 小于number，array_to_search变成如下状态：
middle = (4 + 7) // 2 = 5，array_to_search[middle ] = 28，小于number，array_to_search变成如下状态：
middle = (6 + 7) // 2 = 6， array_to_search[middle ] = 34，等于number，算法结束
查找失败
middle = (0 + 7) // 2 = 3，array_to_search[middle ] = 16， 大于number，array_to_search变成如下状态：
middle = (0 + 2) // 2 = 1，array_to_search[middle ] = 7，大于number，array_to_search变成如下状态：
middle = (0 + 0) // 2 = 0，array_to_search[middle ] = 1，小于number，由于问题规模已经为1，算法结束，查找失败。
流程图
完整算法（Python实现）
from random import uniform
def binary_search(array_to_search, number, left, right):
index = -1
while(left <= right):
middle = (left + right) // 2
if array_to_search[middle] == number:
index = middle
break
elif array_to_search[middle] > number:
right = middle - 1
else:
left = middle + 1
return index
if __name__ == '__main__':
array_size = int(input("Please input the length of array:"))
array_to_search = [int(uniform(0, 5)) + 5 * i for i in range (0, array_size)]
print("Init array:", array_to_search)
number = int(input("Please input the number you want to search:"))
# start search
print("\n\n")
print("######################")
print("## Start searching! ##")
print("######################")
print("")
print("Binary Search:", binary_search(array_to_search, number, 0, len(array_to_search)))时间复杂度
对于一个长度为n的数组，每次与中间元素进行比较后规模都将缩小为原来的\(\frac{1}{2}\)，因此经过\(\log_2n\)次比较后，规模将会缩小为1，因此二分查找的时间复杂度为\(O(\log_2n)\)。