關於搜索的算法問題

9.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

二分搜索

問題：在已排序的數組中搜索元素： 給定一個已排序的數字數組和一個目標值。需要找到目標值在數組中的索引。

解決方案： 使用二分搜索將數組分成兩半並搜索目標值。

實現範例：

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

9.2 使用哈希表優化搜索的問題

1. 搜索數組中的重複項

問題： 給定一個數字數組。需要找到並返回數組中的所有重複項。

解決方案： 使用哈希表來跟踪已經遇到的數字。如果數字再次出現，將其添加到重複列表中。

實現範例：

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用範例
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # 輸出: [2, 4]

2. 查找具有指定總和的對

問題： 給定一個數字數組和一個目標總和。需要找到所有數字對，使其總和等於目標值。

解決方案： 使用哈希表存儲數字並檢查它們是否與當前數字形成目標總和的對。

實現範例：

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# 使用範例
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # 輸出: [(1, 5), (7, -1), (1, 5)]

9.3 綜合使用不同的搜索方法

在複雜的問題中，通常需要使用多種搜索方法以達到最佳效率。綜合使用線性搜索、二分搜索和哈希表可以更有效和靈活地解決問題。

範例 1：在數組中搜索元素並檢查其在另一個數組中的存在性

給定兩個數字數組。需要找到第一個數組中存在於第二個數組中的元素。

解決方案：

• 使用哈希表存儲第二個數組的元素。
• 對於第一個數組中的每個元素，檢查其在哈希表中的存在性。

實現範例：

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # 第二個數組的哈希表
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# 使用範例:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # 輸出: [3, 4, 5]

範例 2：檢查子數組是否為哈希表中模式的字母移位

給定一個字符串數組和一個模式字符串。需要檢查字符串數組中是否存在某個子字符串是該模式的字母移位。

解決方案：

• 使用哈希表計算模式中字符的頻率。
• 遍歷字符串數組並使用「滑動窗口」檢查每個子字符串是否符合字符頻率。

實現範例：

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# 使用範例:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # 輸出: True

9.4 實踐任務來鞏固知識

任務 1：在未排序的數組中搜索元素

給定一個數字數組和一個目標值。需要找到目標值在數組中的索引。使用線性搜索。

範例：

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

# 使用範例:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # 輸出: 2

任務 2：在數組中搜索重複項

給定一個數字數組。使用哈希表找到並返回數組中的所有重複項。

範例：

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# 使用範例:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # 輸出: [3, 1]