Skip to main content

Binary Search

線性搜尋 vs. 二分搜尋

二分搜尋（Binary Search）是一種高效的搜尋演算法，用於在已排序的串列（List）中尋找特定元素的位置或值。

前提條件：

資料集合必須是已排序的，可以是升序或降序排列。這是因為二分搜尋利用了排序順序來有效地縮小搜索範圍。

步驟：

  1. 初始化左右邊界：將搜尋範圍的左邊界 left 設為 0，右邊界 right 設為資料集合的最後一個元素的索引。
  2. 重複以下步驟，直到左邊界 left 大於右邊界 right：
    • 計算中間索引 mid，可以使用 mid = (left + right) // 2。
    • 檢查中間元素 arr[mid] 與目標元素 target 的比較：
      • 如果 arr[mid] 等於 target，則找到目標元素，返回 mid。
      • 如果 arr[mid] 大於 target，則將右邊界 right 設為 mid - 1，縮小搜索範圍為左半部分。
      • 如果 arr[mid] 小於 target，則將左邊界 left 設為 mid + 1，縮小搜索範圍為右半部分。
  3. 如果搜索範圍內找不到目標元素，則返回 -1，表示目標元素不存在於數列中。

特點：

  • 二分搜尋是一種高效的搜尋演算法，因為它可以在每次迭代中將搜索範圍縮小一半，而不是線性搜索逐一檢查每個元素。
  • 時間複雜度為 O(log n)，其中 n 是資料集合中的元素數量。因此，二分搜尋適用於大型排序數列。
  • 二分搜尋通常用於數列搜尋，但也可以應用於其他已排序的數據結構，如二叉搜尋樹。

二分搜尋是一個高效的搜尋演算法，特別適用於已排序的數列中尋找目標元素。它的主要優勢在於其快速的搜索速度，特別在大型資料集合中表現出色。

def linear_search(list, key):
    """If key is in the list returns its position in the list,
       otherwise returns -1."""
    for i, item in enumerate(list):
        if item == key:
            return i
    return -1
def binary_search(list, key):
    """Returns the position of key in the list if found, -1 otherwise.

    List must be sorted.
    """

    # Sort the List
    list.sort()                       # 排序串列
    left, right = 0, len(list) - 1    # 初始化左右邊界
    
    while left <= right:
        middle = (left + right) // 2  # 計算中間索引
        
        if list[middle] == key:
            return middle             # 找到目標元素，傳回索引位置
        if list[middle] > key:
            right = middle - 1        # 調整右邊界值，縮小搜索範圍為左半部分
        if list[middle] < key:
            left = middle + 1         # 調整左邊界，縮小搜索範圍為右半部分
    return -1                         # 目標元素不存在於數列中，返回-1


# 測試
my_list = [2, 4, 7, 12, 15, 21, 30, 34, 42]
target_number = 15

result = binary_search(my_list, target_number)

if result != -1:
    print(f"目標數字 {target_number} 存在於數列中，索引位置為 {result}")
else:
    print(f"目標數字 {target_number} 不存在於數列中")
使用案例
  1. 查找元素： 最常見的用途是在已排序的數列或列表中查找特定的元素。因為數據已經排序，所以你可以迅速縮小搜索範圍，從而實現快速查找。
  2. 字典或詞彙搜尋： 在字典或詞彙中查找單詞或詞彙時，可以使用二分搜尋，特別是當詞彙是按字母順序排列時。
  3. 庫存管理系統： 在庫存管理系統中，你可以使用二分搜尋來查找特定產品或物品的庫存信息。庫存項目通常按照產品編號或名稱排序。
  4. 數學方程求解： 在數學應用中，你可以使用二分搜尋來解方程或找到方程的根。通過不斷縮小可能的解的範圍，可以高效地找到解。
  5. 遊戲開發： 在遊戲中，你可以使用二分搜尋來實現各種功能，如查找玩家在排行榜中的位置、確定物體是否在特定範圍內等。
  6. 日曆應用： 在日曆應用中，你可以使用二分搜尋來查找特定日期，尤其是當日期已按日期順序排列時。
  7. 簡單排序： 雖然二分搜尋主要是一個查找搜尋演算法，但也可以在排序中使用。你可以使用二分搜尋來找到應該插入的位置，以實現插入排序。
  8. 音樂播放器： 在音樂播放器中，你可以使用二分搜尋來查找特定歌曲或歌手，特別是當音樂庫已按標題或藝術家名稱排序時。
  9. 路線規劃： 在地圖或路線規劃應用中，你可以使用二分搜尋來查找最接近的地點或路徑，以提高搜索速度。

Back to top