🔎查找算法

查找算法是计算机科学中用来在数据集合中查找特定元素的方法。查找算法是程序设计和数据处理中的核心部分，决定了数据访问的效率。常见的查找算法根据数据是否有序、数据结构不同，效率差异很大。

一、顺序查找（线性查找）

1. 基本思想

顺序查找是一种最简单的查找方法，逐个检查数据集合中的元素，直到找到目标元素或者遍历完所有元素。

2. 适用场景

• 数据无序或无索引时适用。
• 数据量较小时可以使用。
• 实现简单，但效率较低。

3. 程序

def sequential_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index  # 找到返回索引
    return -1  # 未找到返回 -1

4. 时间复杂度

• 最好情况：O(1)（目标在第一个位置）
• 平均和最坏情况：O(n)（需要遍历整个数组）

5. 空间复杂度

• O(1)，只使用固定的几个变量。

---

二、二分查找（折半查找）

1. 基本思想

二分查找要求数据必须有序。它通过反复将查找区间分成两半，逐步缩小范围，直到找到目标元素或查找区间为空。

2. 适用场景

• 有序数组。
• 数据量较大时比顺序查找效率高得多。

3. 程序

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  # 未找到

4. 时间复杂度

• 最好、平均、最坏情况均为：O(log n)

5. 空间复杂度

• O(1)，只用常数空间。

---

三、插值查找

1. 基本思想

插值查找也是基于有序数组，和二分查找类似，但计算分割点时利用目标值和数组值的比例关系，更适合均匀分布的数据。

计算分割点公式：

$$mid=low+\frac{(high-low)\times (target-arr[low])}{arr[high]-arr[low]}$$

• low 和 high 是当前查找区间的左右索引。
• arr[low] 和 arr[high] 是这个区间中对应的数值范围。
• (target - arr[low]) 表示目标值相对于区间起点的偏移。
• arr[high] - arr[low] 表示区间内数值的总跨度。
• (high - low) 是当前区间的长度（索引差）。

公式本质上是用线性插值的方法，估算目标值 target 在数组区间里的大致位置。

流程:

初始条件：
low = 0, high = 9 计算 mid：

$$mid=low+\frac{(high-low)\times (target-arr[low])}{arr[high]-arr[low]}=0+\frac{(9-0)\times (70-10)}{100-10}=0+\frac{9\times 60}{90}=0+6=6$$

比较 arr[6] = 70 和目标值 70，找到目标，返回下标 6。 如果目标是 65：
low = 0, high = 9 计算 mid：

$$mid=0+\frac{(9-0)\times (65-10)}{100-10}=0+\frac{9\times 55}{90}=5.5\approx 5$$

比较 arr[5] = 60 < 65，更新 low = mid + 1 = 6。 重新计算 mid：

$$mid=6+\frac{(9-6)\times (65-70)}{100-70}=6+\frac{3\times (-5)}{30}=6-0.5=5.5\approx 6$$

比较 arr[6] = 70 > 65，更新 high = mid - 1 = 5。 现在 low = 6 > high = 5，查找失败。

2. 适用场景

• 有序且均匀分布的数据。

• 数据分布不均匀时，效率下降，可能退化到 O(n)。比如在[1, 2, 3, 4, 5, 6, 7, 8, 9, 10000] 数列查找 10。

3. 程序

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and target >= arr[low] and target <= arr[high]:
        if low == high:
            if arr[low] == target:
                return low
            return -1
        mid = low + ((high - low) * (target - arr[low])) // (arr[high] - arr[low])
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

4. 时间复杂度

• 最好情况：O(log log n)
• 平均情况：接近 O(log log n)
• 最坏情况：O(n)

5. 空间复杂度

• O(1)，只使用固定变量。

---

四、斐波那契查找

1. 斐波那契数列介绍

斐波那契数列是由意大利数学家列昂纳多·斐波那契发现的一个数列，定义如下： 斐波那契数列定义如下：

$$F_0=0,F_1=1$$$$F_n=F_{n-1}+F_{n-2}(n\ge 2)$$

数列开始为：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

斐波那契数列在自然界和计算机科学中都有广泛应用。

2. 斐波那契数列的实现

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b

3. 斐波那契查找原理

斐波那契查找使用斐波那契数列来划分查找区间，减少对中点的计算，适合分布较均匀的有序数组。它通过斐波那契数列确定比较位置，比二分查找更依赖斐波那契数的特性。

1. 准备阶段： 找一个斐波那契数 F[k]，满足 F[k] >= 数组长度 n。如果数组长度不是斐波那契数，就用 F[k] - n 的位置补全数组（实际查找时不用真的补，只是方便理解）。
2. 比较位置的选择： 用 F[k-2] 作为当前要比较的下标（起点是0），这是因为斐波那契数的性质让我们可以减少后续查找的范围。
3. 查找步骤：
   • 比较目标值和 arr[F[k-2]] 位置的元素。
   • 如果相等，返回结果。
   • 如果目标值小，向左子区间移动： 这时查找区间变成前 F[k-2] 个元素，更新 k 为 k-2。
   • 如果目标值大，向右子区间移动： 查找区间变成后面 F[k-1] 个元素，更新 k 为 k-1，同时移动起点（起始索引）到 F[k-2] + 1。
4. 重复以上过程，直到找到或者范围为空。

流程：

假设有一个有序数组（长度10）：

arr = [2, 4, 7, 10, 13, 18, 21, 26, 30, 35]

目标查找值：18

---

第一步：找斐波那契数

数组长度 n=10，找一个 F[k] >= 10 的斐波那契数：

F0=0 F1=1 F2=1 F3=2 F4=3 F5=5 F6=8 F7=13 ← 满足条件（13 >= 10）

所以 k=7，F7=13。

第二步：初始化

offset = -1 （表示已排除的左边元素位置，初始无排除）

第三步：开始比较

• 计算比较下标：i = min(offset + F[k-2], n-1) = min(-1 + F5, 9) = min(-1 + 5, 9) = 4
• 比较 arr[4] = 13 和目标 18

第四步：判断

• 目标18 > 13
• 说明目标在右边，排除前面部分
• 更新：
  • k = k-1 = 6
  • offset = i = 4

第五步：下一轮比较

• i = min(offset + F[k-2], n-1) = min(4 + F4, 9) = min(4 + 3, 9) = 7
• 比较 arr[7] = 26 和目标 18

第六步：判断

• 目标18 < 26
• 目标在左边
• 更新：
  • k = k-2 = 4
  • offset 不变，还是4

第七步：下一轮比较

• i = min(offset + F[k-2], n-1) = min(4 + F2, 9) = min(4 + 1, 9) = 5
• 比较 arr[5] = 18 和目标 18

第八步：找到目标

• arr[5] == 18，查找成功，返回下标5。

4. 程序

def fibonacci_search(arr, target):
    n = len(arr)
    fibMMm2 = 0  # (m-2)th Fibonacci No.
    fibMMm1 = 1  # (m-1)th Fibonacci No.
    fibM = fibMMm2 + fibMMm1  # mth Fibonacci
    
    while fibM < n:
        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1
    
    offset = -1
    
    while fibM > 1:
        i = min(offset + fibMMm2, n - 1)
        
        if arr[i] < target:
            fibM = fibMMm1
            fibMMm1 = fibMMm2
            fibMMm2 = fibM - fibMMm1
            offset = i
        elif arr[i] > target:
            fibM = fibMMm2
            fibMMm1 = fibMMm1 - fibMMm2
            fibMMm2 = fibM - fibMMm1
        else:
            return i
    
    if fibMMm1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1
    
    return -1

5. 时间复杂度

• 最好、平均和最坏情况均为 O(log n)

6. 空间复杂度

• O(1)，使用固定的几个变量。

五、二叉搜索树查找

1. 二叉树简介

二叉树是一种重要的数据结构，由节点组成。每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树节点通常包含三个部分：

• 节点值（key）
• 左子树指针
• 右子树指针

二叉树是许多复杂数据结构的基础，如二叉搜索树、堆、平衡树等。

2. 二叉搜索树（BST）定义

二叉搜索树是一种特殊的二叉树，满足：

• 左子树所有节点的值都小于根节点值。
• 右子树所有节点的值都大于根节点值。
• 左右子树也分别是二叉搜索树。

这种结构支持快速查找、插入和删除操作。

3. 二叉树搜索树的优点

排序后的数组查找很快，二分查找能在 O(log n) 时间内找到元素。但是：

• 插入和删除操作慢： 数组插入或删除元素，需要移动后续元素，时间复杂度是 O(n)，尤其数据量大时很明显。
• 数据是动态变化的： 如果你的数据频繁变化（插入、删除），每次都排序是很浪费资源的

3. 二叉树节点实现

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

4. 一颗二叉树的实现

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

"""
      10
     /  \
    5    15
   /
  3

"""       

# 构建二叉树
root = Node(10)
root.left = Node(5)
root.right = Node(15)

root.left.left = Node(3)

# 简单测试，打印根和左右孩子的值
print("根节点:", root.key)
print("左子节点:", root.left.key)
print("右子节点:", root.right.key)

在实际的程序中，对于一个数列如果我们要用二叉树来实现，通常不会使用 rootroot.left.left这种写法，否则树只要稍微复杂一点，代码就会变得很冗长，一般可以使用递归的方式，让程序给我们自动插入数值：

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

# 创建树
root = None
for key in [10, 5, 15, 3]:
    root = insert(root, key)

5. 二叉搜索树查找实现

def bst_search(root, target):
    if root is None or root.key == target:
        return root
    elif target < root.key:
        return bst_search(root.left, target)
    else:
        return bst_search(root.right, target)

6. 时间复杂度

• 最好情况（树平衡）：O(log n)
• 最坏情况（树退化成链表）：O(n)

7. 空间复杂度

• 递归调用会使用栈空间，最大递归深度为树的高度 h。
• 空间复杂度为 O(h)，
  • 平衡树时 h ≈ log n，空间复杂度为 O(log n)
  • 退化链表时 h ≈ n，空间复杂度为 O(n)