Python - 二元搜尋法
Binary Search 是一種在已排序的陣列中,尋找特定元素的演算法。
是一種很有效率的搜尋算法,在排序過後的資料結構中搜尋數值。其時間複雜度為 O(log n),比線性搜尋的 O(n) 更好。
演算法
Binary Search 的演算法如下:
- 先找到陣列的中間元素
- 將中間元素與目標元素比較
- 如果中間元素等於目標元素,則回傳中間元素的 index
- 如果中間元素大於目標元素,則將中間元素的左邊旗標當作新的較小搜尋範圍,重複步驟 1
- 如果中間元素小於目標元素,則將中間元素的右邊旗標當作新的較小搜尋範圍,重複步驟 1
- 如果左邊旗標大於右邊旗標,則回傳 -1 (找不到目標元素)
實作
在接下來的實作範例中,我們將會試圖使用幾種不同的方式來實作 Binary Search。
使用 while 迴圈
以下是我自己實作的 Binary Search,可以參考一下。
1 | def binary_search(nums, target): |
使用遞迴
以下是使用遞迴的實作方式,可以參考一下。
1 | def binary_search(nums, target, left, right): |
使用 bisect 模組
Python 有內建的 bisect 模組,可以幫助我們實作 Binary Search。
1 | import bisect |
如果你需要 bisect 模組更詳細的介紹,可以參考這篇文章 Python bisect 模組介紹。