搜索算法题

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]