線性和二元搜尋範例

3.1 使用線性搜尋在陣列中找到元素的任務

任務： 給定一個數字陣列，需要使用線性搜尋找到給定數字的索引。如果找不到該數字，則返回-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
result = linear_search(arr, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 7 找到於索引 2

# 未在陣列中找到元素的使用範例:
target = 5
result = linear_search(arr, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 5 找到於索引 -1

說明：

• 函數 linear_search 逐一檢查陣列 arr 的每一個元素並與 target 進行對比。
• 如果找到元素，則返回其索引。
• 如果所有元素都檢查過且未找到目標值，則函數返回-1。

步驟：

1. 陣列 [4, 2, 7, 1, 9, 3] 和目標值 7。
2. 開始搜尋：比較首個元素 (4) 和 7 — 不一致。
3. 移至下一個元素 (2) — 不一致。
4. 移至下一個元素 (7) — 一致。
5. 返回索引 2。

3.2 使用二元搜尋在排序陣列中找到元素的任務

任務： 給定一個已排序的數字陣列，需要使用二元搜尋找到給定數字的索引。如果找不到該數字，則返回-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
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 7 找到於索引 3

# 未在陣列中找到元素的使用範例:
target = 6
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 6 找到於索引 -1

說明：

• 函數 binary_search 使用兩個指標 (left 和 right) 來跟蹤陣列 arr 中的搜尋範圍。
• 在每次迭代中，找到陣列的中間元素並與 target 進行對比。
• 如果中間元素等於 target，則返回其索引。
• 如果 target 小於中間元素，搜尋在陣列的左半部繼續。
• 如果 target 大於中間元素，搜尋在陣列的右半部繼續。
• 如果搜尋範圍交錯且未找到目標，則返回-1。

步驟：

1. 已排序的陣列 [1, 3, 5, 7, 9, 11, 13] 和目標值 7。
2. 搜尋的初始範圍：left = 0, right = 6。
3. 找到中間元素：mid = (0 + 6) // 2 = 3。
4. 比較中間元素 (7) 和 target (7) — 一致。
5. 返回索引 3。

3.3 比較和選擇適合不同任務的搜尋算法

比較線性和二元搜尋：

選擇適合的算法

線性搜尋：

• 當資料未排序時使用。
• 適用於小型陣列或列表。
• 適用當元素數量不多且執行時間不重要時。

二元搜尋：

• 當資料已排序時使用。
• 適合於大型陣列，當搜尋速度重要時。
• 如果需要在相同資料集上頻繁進行搜尋，則效率高（可以預先排序資料）。

3.4 實際任務以鞏固材料

任務 1: 線性搜尋

給定一個數字陣列。寫一個函數來使用線性搜尋找到給定數字。函數應返回找到的元素的索引或 -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
result = linear_search(arr, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 7 找到於索引 2

# 額外測試:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

任務 2: 二元搜尋

給定一個已排序的數字陣列。寫一個函數來使用二元搜尋找到給定數字。函數應返回找到的元素的索引或 -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
result = binary_search(sorted_array, target)
print(f"元素 {target} 找到於索引 {result}")  # 輸出: 元素 7 找到於索引 3

# 額外測試:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

任務 3: 線性與二元搜尋比較

給定一個數字陣列。寫兩個函數來搜尋給定數字：一個使用線性搜尋，另一個使用二元搜尋。在大陣列中比較兩個函數的效能。

範例：

import time
import random

# 線性搜尋
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -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

# 生成大型陣列
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# 性能比較
start_time = time.time()
linear_search(large_array, target)
print(f"線性搜尋耗時: {time.time() - start_time:.6f} 秒")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"二元搜尋耗時: {time.time() - start_time:.6f} 秒")