Skip to main content

Binary Search

二分搜尋（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} 不存在於數列中")
Example2: Binary Search
def find_item(list, item):
  #Returns True if the item is in the list, False if not.
  if len(list) == 0:
    return False

  list.sort()
  #Is the item in the center of the list?
  middle = len(list)//2
  if list[middle] == item:
    return True

  #Is the item in the first half of the list? 
  if item < list[middle]:
    #Call the function with the first half of the list
    return find_item(list[:middle], item)
  else:
    #Call the function with the second half of the list
    return find_item(list[middle+1:], item)

  return False

list_of_names = ["Parker", "Drew", "Cameron", "Logan", "Alex", "Chris", "Terry", "Jamie", "Jordan", "Taylor"]

print(find_item(list_of_names, "Alex")) # True
print(find_item(list_of_names, "Andrew")) # False
print(find_item(list_of_names, "Drew")) # True
print(find_item(list_of_names, "Jared")) # False

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

    #Initialize the counter of steps
    steps=0
    for i, item in enumerate(list):
        steps += 1
        if item == key:
            break
    return steps 

def binary_search(list, key):
    #Returns the number of steps to determine if key is in the list 

    #List must be sorted:
    list.sort()

    #The Sort was 1 step, so initialize the counter of steps to 1
    steps=1

    left = 0
    right = len(list) - 1
    while left <= right:
        steps += 1
        middle = (left + right) // 2
        
        if list[middle] == key:
            break
        if list[middle] > key:
            right = middle - 1
        if list[middle] < key:
            left = middle + 1
    return steps 

def best_search(list, key):
    steps_linear = linear_search(list, key) 
    steps_binary = binary_search(list, key) 
    results = "Linear: " + str(steps_linear) + " steps, "
    results += "Binary: " + str(steps_binary) + " steps. "
    if (steps_linear < steps_binary):
        results += "Best Search is Linear."
    elif (steps_linear > steps_binary):
        results += "Best Search is Binary."
    else:
        results += "Result is a Tie."

    return results

print(best_search([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 1))
#Should be: Linear: 1 steps, Binary: 4 steps. Best Search is Linear.

print(best_search([10, 2, 9, 1, 7, 5, 3, 4, 6, 8], 1))
#Should be: Linear: 4 steps, Binary: 4 steps. Result is a Tie.

print(best_search([10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 7))
#Should be: Linear: 4 steps, Binary: 5 steps. Best Search is Linear.

print(best_search([1, 3, 5, 7, 9, 10, 2, 4, 6, 8], 10))
#Should be: Linear: 6 steps, Binary: 5 steps. Best Search is Binary.

print(best_search([5, 1, 8, 2, 4, 10, 7, 6, 3, 9], 11))
#Should be: Linear: 10 steps, Binary: 5 steps. Best Search is Binary.

 

No Comments
Back to top