每天學習一點兒演算法--二分查找

05-15

演算法是什麼？

演算法就是完成一組特定任務的方法。

比如將大象放進冰箱需要三步：

打開冰箱
將大象放進冰箱
關閉冰箱

這就是一種演算法。

如果用計算機語言來敘述，就是任何實現某種功能的代碼片段都可以稱之為演算法。

一個程序員應該掌握大概50種基本演算法，但目前我們屬於初級階段，先掌握一些簡單有趣的演算法，為日後進一步的演算法學習打下基礎。

二分查找

比如我要在字典（這裡是真實的字典，不是Python的dict類型）中查找以O為拼音首字母的漢字，我會從字典的中間附近開始翻閱，因為我知道字母O在26個字母的中間附近，這會提高我的查找效率。在這裡，我就運用了二分查找的思想。

二分查找是一種演算法，它的思想就是：

在一個有序的元素列表中，每次將查找的元素與元素列表的中間元素作比較
如果等於中間元素，則查找完畢
若比中間元素大，則在大於中間元素的一半中重複步驟1
若比中間元素小，則在小於中間元素的一半中重複步驟1
重複步驟2或3或4，直至查找完畢

注釋：僅當列表是有序的時候，二分查找才管用。

一般而言，對於包含n個元素的有序列表，用二分查找最多需要㏒?n步，而簡單查找最多需要n步。

我們一般使用大O表示法來表徵演算法的運行時間，其中㏒一般指的是㏒?

現在我們來看看如何使用Python來編寫二分查找的代碼，這裡以一個簡單的數組示例：

def binary_search(list, item): """定義一個二分查找的函數""" # low 和 high用於跟蹤要在其中查找的列表部分 low = 0 high = len(list) - 1 while low <= high: global n mid = int((low + high)/2) # 檢查中間的元素 guess = list[mid] n = n + 1 # 時間複雜度計數 if guess == item # 找到了元素 return mid elif guess > item: # 猜的數大了 high = mid - 1 else: # 猜的數小了 low = mid + 1 return None # 沒有查詢到指定的元素 n = 0 my_list = [1, 3, 5, 7, 9, 10]result = binary_search(my_list, 7) # 指定元素的位置 print("查詢結果：", result)print("時間複雜度：", n)</pre>

執行結果：

查詢結果： 3時間複雜度： 3

需要說明的是，二分查找的查詢結果是返回待查找元素在列表中的位置，當然，列表是以0開始標記的。

大O表示法

大O表示法是一種特殊的表示法，它指出了演算法的運行速度有多快。例如，假設列表包含n個元素，簡單查找需要檢查每個元素，因此需要執行n次操作，使用大O表示法，它的運行時間為O(n)，它的單位是秒么？不是，它沒有單位。

大O表示法指的並非以秒為單位的速度。它指的是演算法運行時間的增速（強調增速）。

比如，為檢查長度為n的列表，二分查找需要執行㏒n次操作。使用大O表示法，它的運行時間為O(㏒n)。

我們來對比一下簡單查找和二分查找的增速差異（假設檢查一個元素需要1毫秒）：

這裡就能看出兩者運行時間的增速有著天壤之別

大O表示法指出的是平均情況下的運行時間

比如，簡單查找的運行時間用大O表示法是O(n)，但是如果列表的第一個元素就是待查找元素，那麼簡單查找的運行時間就是O(1)。但這只是特殊情況，一般而言，簡單查找的運行時間是O(n)。

一些常見的大O運行時間

下面從快到慢列舉了5種常見的大O運行時間

O(㏒ n)，也叫對數時間，這樣的演算法包括二分查找
O(n)，也叫線性時間，這樣的演算法包括簡單查找
O(n*㏒n)，這樣的演算法包括快速排序--一種速度較快的排序演算法
O(n2)，這樣的演算法包括選擇排序--一種速度較慢的排序演算法
O(n!)，這樣的演算法包括旅行商問題的解決方案--一種非常慢的演算法

旅行商問題

旅行商問題是計算機科學領域一個十分著名的問題。這個問題是怎樣的呢？

有一位旅行商，他要前往5個城市。

畫的圖好醜

同時要確保旅程最短。為此，可以考慮去往這些城市的各種可能順序。高中學過的排列組合的知識告訴我們，5個城市有120種不同組合。因此，在涉及5個城市時，需要執行120次操作。涉及6個城市時，需要執行720次操作。

推而廣之，涉及n個城市時，需要執行n！（n的階乘）次操作才能計算出結果。因此運行時間為O(n!)，即階乘時間。在涉及的城市較多時，這個演算法根本無法在有效的時間內計算出結果。面對這種問題，我們只能去找出近似答案~

小結

二分查找的速度比簡單查找快得多
演算法的運行時間不是以秒為單位的
演算法的運行時間是從其增速的角度衡量的
演算法的運行時間使用大O表示法表示

每天學習一點點，每天進步一點點。