當您要檢查某個元素是否在列表中時，有很多方法可以解決相同的問題。可以通過線性查找和二分查找來完成，但是要猜測哪個更快。
為什麼？
如果你最近參加過面試，你就會知道二分查找是面試官的最愛。
您為什麼要花時間學習二分查找？ C ++編程朋友可能已經告訴過您。 Python很慢。 您想確保自己的程序不會比所需的速度慢。
學習Python時，您將學習進行線性查找以檢查元素是否在列表中。 當您學習編碼時很好，但是如果列表中有60.000.000個元素會發生什麼呢？
如果在包含11個元素的列表中進行線性查找，則必須遍歷所有11個元素。 如果您使用二分查找，最終可能要進行2次迭代，具體取決於您要查找的內容。 請參見下面的圖形。
顯而易見，哪種方法更快。
開始學習Python時，您很可能已經使用了一百次列表。 檢查列表中是否有一個值是一項正常的任務，您之前已經看到過：
my_list = [1,2,3,3,5,11,12]if 11 in my_list:return Truereturn False
或者
my_list = [1,2,3,3,5,11,12]for each in list:if each==11: return Truereturn False
讓我們開始看看如何實現二分查找。
怎麼做?
讓我們看看二分查找是如何工作的。
首先，我們需要確保列表是有序的。您可以使用.sort()或sorts()對列表進行排序，我使用.sort()在適當的地方修改列表。如果出於某種原因需要一個新列表，或者不想篡改原始列表，可以使用sorted()
這是我們的測試內容:
bin_list = [1,2,3,5,6,9,11,12,15,20,22]search_value_a = 15
我們要尋找15的值。
我們的起點。具有最小值和最大值的列表:
當我們做二分查找時，我們從尋找列表中的中間元素開始:
中間索引為5，值為9。首先我們要知道9是不是我們要找的數字。記住，我們要找的是15。如果不是，我們檢查它是更高還是更低。在這個例子中，9比15小，所以我們需要設置一個新的最小值點。我們知道我們不再需要擔心列表的下半部分。新的最小點將被設置為列表上部的第一個可能的項。
使用新的中點，我們檢查這是否是我們要尋找的數字。在這種情況下，正好是15，這樣這次查找就完成了。
如果我們要找的是2，而第一個中間值是9，你覺得這個算法會怎麼做?你是對的。取而代之的是max指數。
代碼
通俗的流程解釋如下：
用列表和目標作為參數創建函數。確保列表是有序的。
獲取列表長度- 1為最大，0為開始。循環將:
獲得新的中間值檢查中間值是否高於或低於目標值。檢查結束後，將最小值或最大值移到中間。如果middle == target，返回True如果我們到達列表的末尾，則目標不在列表中下面看看代碼實現：
mport randomdef binary_search(input_list , target_value):''' Function executing binary search to find if element is in a list. parameters: - list - target return value: True/False (bool) ''' input_list.sort() min_index = 0 max_index = len(input_list) -1 while max_index >= min_index: mid_index =(max_index+min_index)//2 if input_list[mid_index] == target_value: return True elif input_list[mid_index] < target_value: min_index = mid_index+1 else: max_index = mid_index-1 return Falsedef main(): #bin_list = list(range(6,501)) bin_list = [1,2,3,5,6,9,11,12,15,20,22] search_value_a = 15 search_value_b = 7 assert binary_search(bin_list,search_value_a) == True assert binary_search(bin_list,search_value_b) == Falseif __name__ == '__main__': main()
我們已經創建了一個具有兩個參數的函數。列表和目標值。目標值就是我們要找的數字。這個列表就是我們要遍歷的，用來尋找數字的列表。
def binary_search(input_list , target_value):
如果我們找到了目標值，我們將返回True。如果不是，我們將返回False。
我們要做的第一件事是對列表進行排序，並定義列表的最小索引和最大索引。
input_list.sort()min_index = 0max_index = len(input_list) -1
我們使用len(list)-1的原因是Python從0開始索引。測試列表的長度是11，但是最後一個索引是[10]。
現在，讓我們進入主要的功能，循環:
while max_index >= min_index:mid_index =(max_index+min_index)//2 if input_list[mid_index] == target_value: return True elif input_list[mid_index] < target_value: min_index = mid_index+1 else: max_index = mid_index-1
只要最大值不大於最小值，我們就繼續。如果循環停止了，那就意味著我們已經摺疊了列表，使得最大值小於最小值。此時，沒有必要查找這個值，因為沒有更多的列表了。
mid被設置為最大值和最小值的平均值。請注意我們是如何使用整數除法的，例如7//2將是3而不是3.5。這樣，我們總是為索引得到一個乾淨的整數。
如果帶有中間索引的列表項的值等於我們的目標值，我們就成功了!返回True，然後退出。
如果這個值小於目標值，我們知道我們必須把最小索引推到那個點。因此新的最小值是中間+1
如果該值不等於或小於目標值，則會較大。這意味著我們可以刪除列表的頂部並將最大索引下壓。max被設置為中間-1
如果您覺得難以理解，可以在代碼中添加print()，以獲得索引跳躍的可視化表示。
在while循環的midindex =(maxindex+min_index)//2之後添加這個:
print (f'min: {min_index} , mid: {mid_index} , max: {max_index}')
但是它更快嗎?
該函數的時間複雜度為O(n)，其中n為鍊表的長度。為了檢驗哪種查找更快，我們可以計算二分查找相對於線性查找的時間。
首先，我們需要寫出一個線性查找函數:
def linear_search(input_list, target_value):for each in input_list: if each==target_value: return True return False
下面我們可以進行對比了：
def binary_performance():run_setup = '''from __main__ import binary_search''' run_code = '''bin_list = list(range(6,501))binary_search(bin_list,15)''' performance = timeit.repeat(setup = run_setup, stmt = run_code, repeat = 3, number = 10_000) print(f'binary search performance = {round(min(performance),2)}')def linear_performance(): run_setup = '''from __main__ import linear_search''' run_code = '''lin_list = list(range(6,501))linear_search(lin_list,15)''' performance = timeit.repeat(setup = run_setup, stmt = run_code, repeat = 3, number = 10_000) print(f'linear search performance = {round(min(performance),2)}')binary_performance()linear_performance()
陷阱
如果您運行上面的代碼(與原始代碼合併)，您將看到線性查找更快了。這是什麼魔法?
有幾個問題給二分查找帶來了困難。
排序
列表的長度
低於目標的值
以上所有因素，讓線性領先。現在讓我們繼續排序，先改變列表長度:
bin_list = list(range(1,10000))lin_list = list(range(1,10000))
線性查找仍然佔上風。讓我們對函數進行排序，並在將列表傳遞給函數之前對其進行排序。(這對線性查找是不公平的，因為線性並不依賴於排序列表)。我們所要做的就是在列表排序時注釋掉它。
二者速度比較接近了。
如果我們將目標值移動到7,500呢?現在我們的偏差很明顯，因為我們真的想讓二分更快。
這次的差異是極端的。下面的最後一個例子將使情況更加公平。
讓我們以隨機長度和隨機目標創建一個隨機列表。然後我們將為這兩個函數運行100,000次。
test_list = list(range(1,random.randint(2,50000)))test_number = random.randint(2,50000)binary_search(test_list,test_number)
現在讓我們運行10萬次!，我相信這些結果。上圖是排序後結果，下圖需要進行排序
總結
二分比線性快嗎?是的，但要看情況而定。
如果有人告訴你二分查找更快，那是因為它通常是更快的。
和往常一樣，你必須看一看設置，不要每次都去找一個單一的解決方案，因為它「是最好的」。
我們從實驗中看到，這取決於你在做什麼。如果您有一個簡短的列表，或者如果您在列表的下半部分尋找元素，那麼執行線性查找可能會更好。
這也是編程之美。你不應該在不知道為什麼的情況下使用一種方法來做某事。如果你還不知道二分查找，現在你有了另一個工具來做查找。只要你覺得它有用，就使用它。
我希望我們能在一件事上達成一致。二分查找是相當酷的!
作者：Martin Andersson Aaberge
deephub翻譯組