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# =排序串列
    0left, 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

Back to top