在計算機科學中，二分查找演算法（binary search）、也稱折半搜索（英語：half-interval search），

二分搜索法、二分搜索、二分探索，是一種在有序數組中查找某一特定元素的搜索演算法。

搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；

如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，

而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。

這種搜索演算法每一次比較都使搜索範圍縮小一半。 (來源於維基百科)

二分查找循環版

#! /usr/bin/pythonn # coding:utf-8nnn def binary_search_while(key, arr):n list 必須是排序好的n 黃哥python培訓_python編程思路之四 諮詢qq:1465376564n http://www.tudou.com/programs/view/Z4IClY5Wj-g/n 運維如何通過學習python學會編程n https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.mdn 黃哥python遠程視頻培訓班n https://github.com/pythonpeixun/article/blob/master/index.mdn 黃哥python培訓試看視頻播放地址n https://github.com/pythonpeixun/article/blob/master/python_shiping.mdn n start = 0n end = len(arr) - 1n while start <= end:n mid = start + (end - start) // 2n if arr[mid] < key:n start = mid + 1n elif arr[mid] > key:n end = mid - 1n else:n return midn return -1nn if __name__ == __main__:n arr = [3, 9, 28, 67, 12, 45]n arr.sort()n print(binary_search_while(12, arr))n print(binary_search_while(3, arr))n print(binary_search_while(9, arr))n print(binary_search_while(99, arr))n

＃二分查找遞歸版

#! /usr/bin/pythonn # coding:utf-8nnn def binary_search_recursion(key, arr, start, end):n list 必須是排序好的n 黃哥python培訓_python編程思路之四 諮詢qq:1465376564n http://www.tudou.com/programs/view/Z4IClY5Wj-g/n 運維如何通過學習python學會編程n https://github.com/pythonpeixun/article/blob/master/python/how_to_learn_python.mdn 黃哥python遠程視頻培訓班n https://github.com/pythonpeixun/article/blob/master/index.mdn 黃哥python培訓試看視頻播放地址n https://github.com/pythonpeixun/article/blob/master/python_shiping.mdn n if start > end:n return -1n mid = start + (end - start) // 2n if arr[mid] > key:n return binary_search_recursion(key, arr, start, mid - 1)n if arr[mid] < key:n return binary_search_recursion(key, arr, mid + 1, end)n return midnnn if __name__ == __main__:n arr = [3, 9, 28, 67, 12, 45]n arr.sort()n print(binary_search_recursion(12, arr, 0, len(arr)-1))n print(binary_search_recursion(3, arr, 0, len(arr)-1))n print(binary_search_recursion(9, arr, 0, len(arr)-1))n print(binary_search_recursion(99, arr, 0, len(arr)-1))n

用途實例：

白名單過濾，有一家商業銀行，將數千萬客戶名單保存為文本文件中，為白名單。

白名單處理成排序好的數組。可以用二分查找演算法快速排除用戶賬號是不是銀行的客戶。

點擊黃哥python培訓試看視頻播放地址

黃哥python遠程視頻培訓班

推薦閱讀：