線性搜尋與二元搜尋的比較

4.1 線性搜尋與二元搜尋的時間複雜度比較

讓我們比較一下線性搜尋和二元搜尋的時間複雜度。

線性搜尋：

• 時間複雜度： O(n)，n 是陣列或串列中的元素數量。
• 最佳情況： O(1) — 元素在第一個位置找到。
• 平均情況： O(n/2) = O(n) — 元素通常在中間位置找到。
• 最差情況： O(n) — 元素在最後一個位置找到或不存在。

二元搜尋：

• 時間複雜度： O(log n)，n 是陣列或串列中的元素數量。
• 最佳情況： O(1) — 元素在第一步找到（中間元素）。
• 平均情況： O(log n) — 搜尋於已排序的陣列中。
• 最差情況： O(log n) — 元素在最後一步找到或不存在。

時間複雜度的分析示例

線性搜尋：

• 陣列 [1, 3, 5, 7, 9, 11, 13]，目標元素是 7。
• 檢查每個元素直到找到索引為 3 的 7。
• 要求 4 個檢查，符合 O(n)。

二元搜尋：

• 陣列 [1, 3, 5, 7, 9, 11, 13]，目標元素是 7。
• 中間元素 (7) 在第一步找到。
• 要求 1 個檢查，符合 O(log n)。

4.2 各方法的優勢與劣勢

讓我們看看各種搜尋方法的優勢與劣勢。

線性搜尋：

優勢：

• 實現簡單：線性搜尋非常容易實現和理解。
• 對數據無要求：線性搜尋可應用於未排序的數據。
• 適合小型陣列：線性搜尋對小型陣列有效。

劣勢：

• 對大型陣列效率低：時間複雜度 O(n) 使其對大型陣列無效。
• 運行時間長：對大型陣列，線性搜尋可能需要很長時間，特別是當目標元素接近尾部或不存在時。

二元搜尋：

優勢：

• 對大型陣列效率高：O(log n) 的時間複雜度使其對大型陣列非常有效。
• 運行快：對已排序的大型陣列，二元搜尋比線性搜尋快得多。

劣勢：

• 需要排序數據：二元搜尋僅對已排序的陣列有效，因此需要額外時間進行初步排序。
• 實現複雜：與線性搜尋相比，二元搜尋的實現更復雜。

4.3 何時使用何種搜尋

考慮什麼情況下使用線性搜尋，什麼情況下使用二元搜尋。

線性搜尋。

當以下條件時使用線性搜尋：

• 陣列或串列未排序。
• 陣列或串列的大小較小。
• 需要簡單快速的解決方案，無需對排序進行額外開銷。
• 要求找到元素的首次出現或所有出現。
• 數據實時輸入，無法或不適合進行初步排序。

二元搜尋。

當以下條件時使用二元搜尋：

• 陣列或串列已排序。
• 陣列或串列的大小較大。
• 頻繁在相同的數據集中搜索元素（可以先對數據進行一次排序）。
• 搜索速度很重要。
• 可以接受花時間對數據進行初步排序。

4.4 線性搜尋的範例問題

1. 搜索未排序的串列

需要在未排序的數字串列中找到指定數字的索引。

範例：

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # 輸出: 2

2. 搜索陣列中的首次出現

需要在字串串列中找到指定元素的首次出現。

範例：

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target))  # 輸出: 1

3. 在實時數據中搜索

在實時流中的數據中找到元素。

範例：

import random

def find_in_stream(stream, target):
    for index, element in enumerate(stream):
        if element == target:
            return index
    return -1

stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))

4.5 二元搜尋的範例問題

1. 搜索已排序陣列

需要在已排序的數字陣列中找到指定數字的索引。

範例：

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # 輸出: 3

2. 大數據集中頻繁搜索

頻繁在大的排序數字陣列中搜索元素。

範例：

import random

sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))

3. 在已排序的資料庫中搜索元素

在已排序的資料庫中根據關鍵字段找到記錄。

範例：

database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
    left, right = 0, len(db) - 1
    while left <= right:
        mid = (left + right) // 2
        if db[mid]["id"] == target_id:
            return db[mid]
        elif db[mid]["id"] < target_id:
            left = mid + 1
        else:
            right = mid - 1
    return None

target_id = 54321
print(binary_search_db(database, target_id))