算法系列15天速成 第六天 五大经典查找【下】

算法系列15天速成 第六天 五大经典查找【下】- 完整攻略

简介

本篇文章是算法系列15天速成中的第六天内容，主要是介绍五大经典查找的后三种查找算法：插值查找、斐波那契查找以及分块查找。在介绍每一种查找算法时都会包含具体的思路、复杂度和应用场景等内容。

插值查找

思路

插值查找是在二分查找的基础上优化的一种查找算法，它不是通过数组的中间元素进行查找，而是通过插值公式计算出要查找的元素的位置。插值公式如下：

mid = left + (right-left)*(value-arr[left])/(arr[right]-arr[left])

其中value是要查找的元素，arr是已排序的数组。

复杂度

插值查找算法的时间复杂度为O(log n)，在特定的情况下，它可以具有比二分查找更高的效率。

应用场景

插值查找可以用于均匀分布的有序数组中。

示例

# 插值查找实现
def interpolation_search(arr, value):
    left, right = 0, len(arr) - 1

    while left <= right and value >= arr[left] and value <= arr[right]:

        mid = left + (right-left)*(value-arr[left])//(arr[right]-arr[left])

        if arr[mid] == value:
            return mid

        elif arr[mid] < value:
            left = mid + 1

        else:
            right = mid - 1

    return -1

# 测试插值查找
arr = [1, 3, 5, 7, 9, 11]
value = 5
print(interpolation_search(arr, value))

斐波那契查找

思路

斐波那契查找是对插值查找算法的进一步优化，它使用斐波那契数列的值来计算要查找的值在数组中的位置。具体来说，要查找的值value在第n个斐波那契数列中出现，使用斐波那契数列的前两个值F(k)和F(k-1)来计算要查找的值在数组中的位置。具体过程可以参考：https://www.cnblogs.com/maybe2030/p/4715035.html

复杂度

斐波那契查找算法的时间复杂度为O(log n)。

应用场景

斐波那契查找可以用于有序数组中。

示例

# 斐波那契查找实现
def fibonacci_search(arr, value):
    left, right = 0, len(arr) - 1

    # 构建斐波那契数列
    fib = [0, 1, 1]
    while fib[-1] < len(arr):
        fib.append(fib[-1] + fib[-2])

    # 在斐波那契数列中寻找 value 对应的位置
    k = 0
    while fib[k+1] < len(arr):
        k += 1
    offset = fib[k-1]
    while True:
        if value > arr[right]:
            return -1
        if value < arr[left]:
            return -1
        if left > right:
            return -1

        mid = left + offset
        if value < arr[mid]:
            right = mid - 1
            offset = offset - fib[k-2]
            k -= 1
        elif value > arr[mid]:
            left = mid + 1
            offset = offset - fib[k-1]
            k -= 2
        else:
            return mid

分块查找

思路

分块查找是一种数据分块技术，它将一个大的数据集分割成若干块，并且每一块的数据是有序的，块与块之间的数据无序，这样做的目的是使得查找的复杂度降低。

复杂度

分块查找算法的时间复杂度为O(sqrt(n))，空间复杂度为O(n)。

应用场景

分块查找可以用于难以排序的大规模数据中。

示例

# 分块查找实现
from math import sqrt, ceil

def block_search(arr, value):
    n = len(arr)                          # 数据集大小
    block_size = ceil(sqrt(n))            # 计算分块块长
    block_num = ceil(n / block_size)      # 计算分块数量

    # 计算块的范围，预处理数据块
    blocks = []
    for i in range(block_num):
        left = i * block_size 
        right = min(left + block_size, n)
        blocks.append({'left': left, 'right': right, 'data': arr[left:right]})

    # 在块内二分查找
    target_block = -1
    for i in range(block_num):
        if arr[blocks[i]['left']] <= value <= arr[blocks[i]['right']-1]:
            target_block = i
            break
    if target_block == -1:
        return -1
    else:
        target_index = binary_search(blocks[target_block]['data'], value)
        return blocks[target_block]['left'] + target_index

# 二分查找
def binary_search(arr, value):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == value:
            return mid
        elif arr[mid] < value:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 测试分块查找
arr = [5, 2, 7, 9, 1, 3, 11, 6, 8, 4, 12, 10]
value = 10
print(block_search(arr, value))

总结

本文介绍了插值查找、斐波那契查找和分块查找算法，这三种查找算法都是在二分查找的基础上进行的优化，分别针对了不同的场景和数据特点进行了优化。这些算法适用的场景也不尽相同，需要根据具体情况选择适合的算法进行使用。