Python - 二元搜尋法

Posted on

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 模組介紹。

也許你也會想看看