Python 查找算法

Python 中常用的查找算法有线性查找、二分查找和哈希查找。

1. 线性查找：逐个遍历待查找的数据集，直到找到目标元素或者遍历完整个数据集。时间复杂度为 O(n)，其中 n 是数据集的大小。

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 返回目标元素的索引
    return -1  # 目标元素不存在

# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
index = linear_search(arr, target)
print(f"目标元素 {target} 的索引是 {index}")

2. 二分查找（也称折半查找）：对于已经排序的数据集，每次将待查找区间缩小一半，直到找到目标元素或者确定目标元素不存在。时间复杂度为 O(log n)，其中 n 是数据集的大小。

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 返回目标元素的索引
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # 目标元素不存在

# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
index = binary_search(arr, target)
print(f"目标元素 {target} 的索引是 {index}")

3. 哈希查找：利用哈希函数将元素映射到哈希表中的位置，然后通过查询哈希表来找到目标元素。哈希查找的时间复杂度为 O(1)，但需要额外的空间来构建和存储哈希表。

def hash_search(arr, target):
    hash_table = {}
    for i in range(len(arr)):
        hash_table[arr[i]] = i
    
    if target in hash_table:
        return hash_table[target]  # 返回目标元素的索引
    else:
        return -1  # 目标元素不存在

# 示例用法
arr = [1, 3, 5, 7, 9]
target = 5
index = hash_search(arr, target)
print(f"目标元素 {target} 的索引是 {index}")

以上是三种常用的查找算法在 Python 中的实现。根据数据集的特点和需求，选择合适的查找算法可以提高查找效率。