介紹

二分搜索是一種在有序數(shù)組中查找某一特定元素的搜索算法。這種搜索算法每一次比較都使搜索范圍縮小一半。

復(fù)雜度

最壞時間復(fù)雜度：O(log n)
最優(yōu)時間復(fù)雜度：O(1)
平均時間復(fù)雜度：O(log n)
最壞空間復(fù)雜度：迭代： O(1) 遞歸：O(log n)

步驟

1. 搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；
2. 如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。
3. 如果在某一步驟數(shù)組為空，則代表找不到。

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