跳轉到

02.6-搜尋法

搜尋法（Search Algorithms）是指在一個集合中查找特定元素或解決方案的算法。搜尋法是計算機科學中非常重要的一類算法，它們的應用範圍非常廣泛，從簡單的線性搜尋到複雜的圖形搜尋，都屬於搜尋算法的範疇。根據問題的特性，搜尋算法可以分為多種不同的類型。

1. 搜尋法的類型#

線性搜尋是一種最簡單的搜尋算法。它的基本思想是從數據結構的起始位置開始，依次檢查每一個元素，直到找到目標元素為止。線性搜尋適用於無序或有序的數據結構。

時間複雜度：最壞情況下是 \(O(n)\) ，其中 \(n\) 是集合中的元素數量。

範例代碼： 

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index  # 找到目標，返回其索引
    return -1  # 如果找不到目標，返回 -1

arr = [3, 5, 7, 9, 2, 8]
target = 7
print(linear_search(arr, target))  # 輸出：2（目標 7 的索引）

二分搜尋是一種高效的搜尋算法，要求數據結構是有序的。它的基本思想是將查詢範圍劃分為兩半，首先檢查中間的元素，如果中間元素是目標元素則返回索引；如果目標元素小於中間元素，則只關注左半部分，否則關注右半部分。這樣可以在每次檢查後將問題規模減半。

時間複雜度： \(O(\log n)\) ，其中 \(n\) 是集合中的元素數量。

範例代碼： 

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  # 如果找不到目標，返回 -1

arr = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(arr, target))  # 輸出：3（目標 7 的索引）

深度優先搜尋是一種圖形搜尋算法，它從圖的起始節點開始，沿著圖的邊走，直到達到最深的節點或目標節點，然後回溯到上一個節點，繼續搜索。DFS 通常使用遞歸實現，並且可以應用於圖形或樹結構的搜尋。

時間複雜度： \(O(V + E)\) ，其中 \(V\) 是圖中的頂點數量， \(E\) 是圖中的邊數量。

範例代碼： 

def dfs(graph, start, target):
    visited = set()
    def dfs_recursive(node):
        if node == target:
            return True  # 找到目標節點
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs_recursive(neighbor):
                    return True
        return False

    return dfs_recursive(start)

# 範例圖的表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

start = 'A'
target = 'F'
print(dfs(graph, start, target))  # 輸出：True（目標 F 可以達到）

廣度優先搜尋是一種圖形搜尋算法，它從圖的起始節點開始，首先訪問所有直接相連的節點，再依次訪問這些節點的相鄰節點。BFS 通常使用隊列來實現，能夠找到最短的路徑（對於無權圖）。

時間複雜度： \(O(V + E)\) ，其中 \(V\) 是圖中的頂點數量， \(E\) 是圖中的邊數量。

範例代碼： 

from collections import deque

def bfs(graph, start, target):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node == target:
            return True  # 找到目標節點
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)

    return False  # 如果找不到目標節點，返回 False

# 範例圖的表示
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

start = 'A'
target = 'F'
print(bfs(graph, start, target))  # 輸出：True（目標 F 可以達到）

2. 搜尋法的比較#

演算法 適用場景 時間複雜度 優點 缺點
線性搜尋 無序數據 \(O(n)\) 實現簡單，適用於無序數據 效率較低，特別是當數據集很大時
二分搜尋 有序數據 \(O(\log n)\) 高效，適用於有序數據 只適用於有序數據
深度優先搜尋 (DFS) 圖形/樹結構 \(O(V + E)\) 能夠遍歷整個圖，適合處理深層結構 可能會遍歷很多無用的節點，佔用較多內存
廣度優先搜尋 (BFS) 圖形/樹結構 \(O(V + E)\) 能找到最短路徑，適合處理廣度較深的結構 需要較多的空間存儲節點

3. 總結#

搜尋法是計算機科學中基礎且重要的算法，用於各種資料結構中查找元素或解決方案。不同的搜尋算法有不同的應用場景，選擇合適的算法取決於數據的結構、大小以及具體需求。在實際應用中，二分搜尋通常是有序數據的首選，DFS 和 BFS 則多用於圖形結構的遍歷和最短路徑搜尋。