介绍

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。这种搜索算法每一次比较都使搜索范围缩小一半。

复杂度

最坏时间复杂度：O(log n)
最优时间复杂度：O(1)
平均时间复杂度：O(log n)
最坏空间复杂度：迭代： O(1) 递归：O(log n)

步骤

1. 搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
2. 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
3. 如果在某一步骤数组为空，则代表找不到。

python

def binary_search(lst, value):
    lo, hi = 0, len(lst)-1
    while lo <= hi:
        mid = (lo + hi) / 2
        if lst[mid] < value:
            lo = mid + 1
        elif value < lst[mid]:
            hi = mid - 1
        else:
            return mid
    return -1
print(binary_search(lst, value))
#递归
def binary_search(arr,start,end,hkey):
    if start > end:
        return -1
    mid = start + (end - start) / 2
    if arr[mid] > hkey:
        return binary_search(arr, start, mid - 1, hkey)
    if arr[mid] < hkey:
        return binary_search(arr, mid + 1, end, hkey)
    return mid