Binary Search

線性搜尋 vs. 二分搜尋

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

前提條件：

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

步驟：

初始化左右邊界：將搜尋範圍的左邊界 left 設為 0，右邊界 right 設為資料集合的最後一個元素的索引。 重複以下步驟，直到左邊界 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，縮小搜索範圍為右半部分。 如果搜索範圍內找不到目標元素，則返回 -1，表示目標元素不存在於數列中。

 

Linear Search

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

Binary Search

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 = 0
    right = 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