Python - 二元搜尋法

Binary Search 是一種在已排序的陣列中,尋找特定元素的演算法。
是一種很有效率的搜尋算法,在排序過後的資料結構中搜尋數值。其時間複雜度為 O(log n),比線性搜尋的 O(n) 更好。

演算法

Binary Search 的演算法如下:

  1. 先找到陣列的中間元素
  2. 將中間元素與目標元素比較
  3. 如果中間元素等於目標元素,則回傳中間元素的 index
  4. 如果中間元素大於目標元素,則將中間元素的左邊旗標當作新的較小搜尋範圍,重複步驟 1
  5. 如果中間元素小於目標元素,則將中間元素的右邊旗標當作新的較小搜尋範圍,重複步驟 1
  6. 如果左邊旗標大於右邊旗標,則回傳 -1 (找不到目標元素)image 106

實作

在接下來的實作範例中,我們將會試圖使用幾種不同的方式來實作 Binary Search。

使用 while 迴圈

以下是我自己實作的 Binary Search,可以參考一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def binary_search(nums, target):
left = 0
right = len(nums) - 1

while left <= right:
mid = (left + right) // 2

if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1

return -1


data = [1, 2, 3, 4, 5, 16, 32, 73, 85, 97]

print(binary_search(data, 73)) # 7
print(binary_search(data, 3)) # 2
print(binary_search(data, 7)) # -1

使用遞迴

以下是使用遞迴的實作方式,可以參考一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def binary_search(nums, target, left, right):
if left > right:
return -1

mid = (left + right) // 2

if nums[mid] == target:
return mid
elif nums[mid] > target:
return binary_search(nums, target, left, mid - 1)
else:
return binary_search(nums, target, mid + 1, right)


data = [1, 2, 3, 4, 5, 16, 32, 73, 85, 97]
size = len(data)

print(binary_search(data, 73, 0, size - 1)) # 7
print(binary_search(data, 3, 0, size - 1)) # 2
print(binary_search(data, 7, 0, size - 1)) # -1

使用 bisect 模組

Python 有內建的 bisect 模組,可以幫助我們實作 Binary Search。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import bisect


def binary_search(nums, target):
index = bisect.bisect_left(nums, target)

if index < len(nums) and nums[index] == target:
return index

return -1


data = [1, 2, 3, 4, 5, 16, 32, 73, 85, 97]

print(binary_search(data, 73)) # 7
print(binary_search(data, 3)) # 2
print(binary_search(data, 7)) # -1

如果你需要 bisect 模組更詳細的介紹,可以參考這篇文章 Python bisect 模組介紹

也許你也會想看看