線性搜尋

1.1 線性搜尋的定義

線性搜尋 (又稱為循序搜尋) 是一種用於在列表或數組中搜尋元素的算法。它會依次檢查每個元素，直到找到匹配的項目或者檢查完所有元素。這是最簡單的搜尋算法，不需要對數據進行預排序。

基本原則：

• 循序檢查： 算法會逐一檢查數組或列表中的每個元素，並將其與目標值進行比較。
• 結束搜尋： 當找到與目標值匹配的元素時，或者所有元素已被檢查完畢，搜尋將結束。
• 不需要排序： 線性搜尋可用於未排序的數據。
• 應用範圍： 線性搜尋可以應用於支持迭代的資料結構，包括列表和數組。

線性搜尋的時間複雜度是O(n)，其中n是數組或列表中的元素數量。在最糟糕的情況下，算法需要檢查所有n個元素，來找到目標值或確定其不存在。

時間複雜度分析：

• 最佳情況 (Best case)： 元素在第一個位置被找到，O(1)。
• 平均情況 (Average case)： 元素在中間位置被找到，O(n/2)，等價於O(n)。
• 最糟情況 (Worst case)： 元素在最後一個位置被找到或不存在，O(n)。

1.2 線性搜尋的逐步實現

線性搜尋步驟：

• 初始化： 設定搜尋的初始索引（通常是零）。
• 循序檢查： 檢查列表或數組中的每個元素，看看是否與目標值匹配。
• 結束條件： 如果找到元素，返回其索引。如果所有元素都被檢查且未找到目標值，返回特定值（通常是-1或None）。

Python中線性搜尋的實現：

def linear_search(arr, target):
    # 遍歷數組中的每個元素
    for index, element in enumerate(arr):
        # 如果當前元素等於目標值，返回其索引
        if element == target:
            return index
    # 如果未找到元素，返回-1
    return -1

實現的逐步解釋：

• 初始化循環： 使用for循環與enumerate函數，每次迭代返回數組的索引和元素。
• 比較： 在每次迭代中，將當前元素與目標值（target）進行比較。
• 返回索引： 如果當前元素等於目標值，則返回該元素的索引。
• 返回-1： 如果循環完成且未找到目標元素，則返回-1。

# 使用示例：
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 7 找到於索引 2

# 在數組中找不到元素的示例：
target = 5
result = linear_search(arr, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 5 找到於索引 -1

1.3 線性搜尋解決的示例問題

線性搜尋可用於解決許多與搜尋數據集合中的元素相關的問題。這裡有一些這樣問題的例子：

問題 1: 搜尋數組中的元素

需要在數字數組中找到給定的數字。

範例：

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

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"元素 {target} 找到於索引 {index}")  # 輸出: 元素 70 找到於索引 3

問題 2: 檢查列表中元素的存在性

需要檢查給定值是否存在於字符串列表中。

範例：

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"元素 {target} {'找到' if found else '未找到'}")  # 輸出: 元素 cherry 找到

問題 3: 搜尋最小或最大元素

需要在列表中找到最小或最大值。

範例：

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"最小值: {min_value}")  # 輸出: 最小值: 2

問題 4: 搜尋第一次出現的位置

找到給定元素在列表中的第一次出現位置。

範例：

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

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"第一次出現 {target} 的索引 {index}")  # 輸出: 第一次出現 2 的索引 1

問題 5: 計算出現次數

計算給定元素在列表中出現的次數。

範例：

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"元素 {target} 出現了 {count} 次")  # 輸出: 元素 2 出現了 3 次