python3 find查找算法|极客笔记

python3 find查找算法

查找算法是计算机科学中的一个重要概念，用于在一个数据集中查找特定元素。在实际编程工作中，经常会用到查找算法，比如在一个数组中查找某个元素是否存在，或者在一个字符串中查找某个子串的位置。

线性查找

线性查找是最简单的一种查找算法，也称为顺序查找。它的原理很简单，就是从头到尾逐个比较每个元素，直到找到目标值为止。如果数据集中有n个元素，最坏情况下需要比较n次才能找到目标值。

下面是一个简单的Python实现：

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 测试
arr = [3, 5, 2, 7, 8, 4]
target = 7
print(linear_search(arr, target))  # 输出：3

上面的代码中，我们定义了一个linear_search函数，参数为一个数组arr和目标值target，使用线性查找算法找到目标值在数组中的位置。在测试代码中，我们传入一个数组arr和目标值7，输出目标值在数组中的位置。

二分查找

二分查找是一种高效的查找算法，前提是数组已经按照升序或降序排好序。它的思想是每次将搜索范围缩小一半，直到找到目标值为止。比较适用于静态数据集或不经常变化的数据集。

下面是一个简单的Python实现：

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

# 测试
arr = [2, 4, 6, 8, 10, 12, 14, 16, 18]
target = 10
print(binary_search(arr, target))  # 输出：4

上面的代码中，我们定义了一个binary_search函数，参数为一个数组arr和目标值target，使用二分查找算法找到目标值在数组中的位置。在测试代码中，我们传入一个已经排好序的数组arr和目标值10，输出目标值在数组中的位置。

哈希查找

哈希查找是一种通过哈希函数来计算元素存储位置的查找算法。它的优点是速度快，可以在常数时间内完成查找操作。但是需要额外的内存空间来存储哈希表。

下面是一个简单的Python实现：

def hash_search(arr, target):
    hash_table = {}
    for i, num in enumerate(arr):
        hash_table[num] = i

    if target in hash_table:
        return hash_table[target]
    else:
        return -1

# 测试
arr = [3, 5, 2, 7, 8, 4]
target = 7
print(hash_search(arr, target))  # 输出：3