前言

在计算机科学中，查找（Search）是最基础也是最核心的操作之一。无论是数据库索引、搜索引擎，还是日常的业务逻辑，高效地定位数据都是提升系统性能的关键。Python 作为一门高级语言，内置了丰富的数据结构（如 list, dict, set），但在面对海量数据或特定约束场景时，理解并手动实现底层的查找算法依然至关重要。

本文将深入解析从最基础的顺序查找到复杂的树形查找（二叉搜索树、AVL树、红黑树），通过10道精选算法题，带你层层递进，掌握查找算法的思想精髓与工程实现。

第一部分：基础线性查找

算法思想基础

线性查找（Linear Search）是最直观的查找方式。它不要求数据有序，只需从头到尾遍历序列，直到找到目标值或遍历结束。

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 适用场景：数据量小、数据无序或链表结构。

题目 1：基础顺序查找与计数

题目描述：给定一个无序整数列表 nums 和一个目标值 target，请实现一个函数，返回目标值在列表中出现的所有索引位置。如果未找到，返回空列表。同时统计比较次数。

算法分析

这是顺序查找的变体。我们需要遍历整个列表，不能像标准二分查找那样找到第一个就停止。我们需要维护一个结果列表来存储所有匹配的索引。

代码实现

文件名称: linear_search_all.py

def linear_search_all(nums, target):
    """
    在无序列表中查找所有目标值的索引
    :param nums: List[int], 输入列表
    :param target: int, 目标值
    :return: Tuple[List[int], int], (索引列表, 比较次数)
    """
    indices = []
    comparisons = 0
    
    for i, num in enumerate(nums):
        comparisons += 1  # 每次循环进行一次比较
        if num == target:
            indices.append(i)
            
    return indices, comparisons

# 测试演练
if __name__ == "__main__":
    data = [5, 3, 8, 3, 9, 3, 1]
    target = 3
    result, comps = linear_search_all(data, target)
    print(f"数据: {data}")
    print(f"目标: {target} -> 索引: {result}, 比较次数: {comps}")

第二部分：有序查找与分治策略

算法思想基础

当数据有序时，我们可以利用“分治法”（Divide and Conquer）大幅减少查找范围。二分查找（Binary Search）是其中的代表，它每次将搜索区间缩小一半。

• 时间复杂度：O(log n)
• 前提条件：数据必须有序（通常是升序）。

题目 2：标准二分查找

题目描述：在一个严格升序的整数数组 nums 中查找 target。如果存在，返回其索引；否则返回 -1。要求使用非递归方式实现。

算法分析

维护两个指针 left 和 right。计算中间位置 mid，比较 nums[mid] 与 target。若相等则返回；若 target 小，则在左半区查找；反之在右半区。注意边界条件的处理，防止死循环。

代码实现

文件名称: binary_search_iterative.py

def binary_search(nums, target):
    """
    非递归二分查找
    :param nums: List[int], 升序列表
    :param target: int, 目标值
    :return: int, 索引或 -1
    """
    left, right = 0, len(nums) - 1
    
    while left <= right:
        # 防止溢出的写法，虽然Python整数不限长，但这是好习惯
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1

# 测试演练
if __name__ == "__main__":
    data = [1, 3, 5, 7, 9, 11, 13]
    print(f"查找 7: 索引 {binary_search(data, 7)}")
    print(f"查找 4: 索引 {binary_search(data, 4)}")

题目 3：寻找旋转排序数组中的最小值

题目描述：假设一个升序数组在某个未知的点进行了旋转（例如 [0,1,2,4,5,6,7] 变为 [4,5,6,7,0,1,2]）。请找出其中最小的元素。

算法分析

这也是二分查找的变种。旋转后的数组分为两个有序段。

1. 比较 mid 和 right 的值。
2. 如果 nums[mid] > nums[right]，说明最小值在右半部分（不包含mid）。
3. 如果 nums[mid] < nums[right]，说明最小值在左半部分（包含mid）。
4. 如果相等（处理重复元素情况），right 减 1 缩小范围。

代码实现

文件名称: find_min_rotated.py

def find_min(nums):
    """
    查找旋转排序数组中的最小值
    :param nums: List[int]
    :return: int
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[right]:
            # 最小值肯定在右侧 (mid+1 ... right)
            left = mid + 1
        elif nums[mid] < nums[right]:
            # 最小值在左侧 (left ... mid)，因为mid可能就是最小值
            right = mid
        else:
            # 处理重复元素，无法判断哪边，缩小右边界
            right -= 1
            
    return nums[left]

# 测试演练
if __name__ == "__main__":
    data = [4, 5, 6, 7, 0, 1, 2]
    print(f"最小值是: {find_min(data)}")

第三部分：插值与斐波那契查找

算法思想基础

除了二分查找，还有根据数据分布特性优化的查找算法。

• 插值查找：类似查字典，根据目标值在范围内的比例估算位置。适用于数据分布均匀的情况。
• 斐波那契查找：利用斐波那契数列分割数组，避免除法运算，仅使用加减法。

题目 4：自适应插值查找

题目描述：在一个分布均匀的升序数组中查找 target。实现插值查找算法，若数据分布极度不均匀导致效率低下，自动退化为二分查找逻辑（本题主要实现标准插值逻辑）。

算法分析

计算公式：pos = low + ((target - nums[low]) * (high - low)) // (nums[high] - nums[low])。
如果 nums[high] == nums[low] 且 target != nums[low]，则直接返回 -1 防止除零。

代码实现

文件名称: interpolation_search.py

def interpolation_search(nums, target):
    """
    插值查找，适用于数据分布均匀的有序数组
    :param nums: List[int]
    :param target: int
    :return: int, 索引或 -1
    """
    low, high = 0, len(nums) - 1
    
    while low <= high and target >= nums[low] and target <= nums[high]:
        if low == high:
            if nums[low] == target:
                return low
            return -1
        
        # 计算预估位置
        # 防止分母为0
        if nums[high] == nums[low]:
            break
            
        pos = low + int(((float(target - nums[low]) / 
                          (nums[high] - nums[low])) * (high - low)))
        
        if nums[pos] == target:
            return pos
        elif nums[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
            
    return -1

# 测试演练
if __name__ == "__main__":
    # 构造一个分布均匀的大数组
    data = [i * 2 for i in range(1000)]
    print(f"查找 500: 索引 {interpolation_search(data, 500)}")

第四部分：哈希查找

算法思想基础

哈希查找（Hash Search）通过哈希函数将键映射到数组索引，理想情况下时间复杂度为 O(1)。核心挑战在于哈希冲突的处理，常见方法有链地址法（Chaining）和开放寻址法（Open Addressing）。

题目 5：设计哈希集合（链地址法）

题目描述：不使用任何内建的哈希表库，设计一个哈希集合（HashSet）。支持 add(key), remove(key), contains(key) 操作。使用链地址法解决冲突。

算法分析

1. 选择一个质数作为桶的数量（如 769）。
2. 哈希函数：key % bucket_count。
3. 每个桶是一个链表（在Python中可用列表模拟）。
4. 添加时检查是否存在，不存在则追加；删除时遍历链表移除；查找时遍历链表。

代码实现

文件名称: hash_set_chaining.py

class MyHashSet:
    def __init__(self):
        """
        初始化哈希集合，使用链地址法
        """
        self.bucket_count = 769  # 选择一个质数
        self.buckets = [[] for _ in range(self.bucket_count)]
    
    def _hash(self, key):
        return key % self.bucket_count
    
    def add(self, key: int) -> None:
        bucket_idx = self._hash(key)
        bucket = self.buckets[bucket_idx]
        if key not in bucket:
            bucket.append(key)
    
    def remove(self, key: int) -> None:
        bucket_idx = self._hash(key)
        bucket = self.buckets[bucket_idx]
        if key in bucket:
            bucket.remove(key)
    
    def contains(self, key: int) -> bool:
        bucket_idx = self._hash(key)
        return key in self.buckets[bucket_idx]

# 测试演练
if __name__ == "__main__":
    hs = MyHashSet()
    hs.add(1)
    hs.add(2)
    print(f"包含 1? {hs.contains(1)}") # True
    print(f"包含 3? {hs.contains(3)}") # False
    hs.remove(1)
    print(f"包含 1? {hs.contains(1)}") # False

第五部分：树形查找基础（BST）

算法思想基础

二叉搜索树（BST）是一种动态数据结构。对于任意节点，左子树所有值小于它，右子树所有值大于它。查找过程类似于二分查找，但在链表式结构中表现更灵活。

• 平均时间复杂度：O(log n)
• 最坏时间复杂度：O(n)（退化成链表时）

题目 6：BST 的查找与插入

题目描述：实现一个二叉搜索树类，包含 search(val) 和 insert(val) 方法。

算法分析

• 查找：从根开始，小于当前值去左边，大于去右边，相等则找到。
• 插入：先查找，找到空位（None）时创建新节点。

代码实现

文件名称: bst_basic.py

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, val):
        """插入节点"""
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert_recursive(self.root, val)
            
    def _insert_recursive(self, node, val):
        if val < node.val:
            if node.left is None:
                node.left = TreeNode(val)
            else:
                self._insert_recursive(node.left, val)
        elif val > node.val:
            if node.right is None:
                node.right = TreeNode(val)
            else:
                self._insert_recursive(node.right, val)
        # 如果相等，通常BST不插入重复值，此处忽略
    
    def search(self, val):
        """查找节点，返回节点对象或None"""
        curr = self.root
        while curr:
            if val == curr.val:
                return curr
            elif val < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return None

# 测试演练
if __name__ == "__main__":
    bst = BinarySearchTree()
    for v in [5, 3, 7, 2, 4, 6, 8]:
        bst.insert(v)
    
    node = bst.search(4)
    print(f"查找 4: {'找到' if node else '未找到'}")
    node = bst.search(10)
    print(f"查找 10: {'找到' if node else '未找到'}")

第六部分：平衡二叉树（AVL）

算法思想基础

为了解决BST在最坏情况下退化为链表的问题，引入了自平衡二叉搜索树。AVL树通过维护每个节点的平衡因子（左子树高度 - 右子树高度，范围为[-1, 0, 1]），在插入或删除后通过旋转（左旋、右旋、左右旋、右左旋）来恢复平衡。

• 时间复杂度：严格保证 O(log n)。

题目 7：AVL 树的插入与平衡维持

题目描述：实现一个AVL树，重点实现插入后的自动平衡逻辑（旋转操作）。

算法分析

1. 像普通BST一样插入节点。
2. 更新路径上节点的高度。
3. 检查平衡因子。如果不平衡（绝对值>1），根据四种情况（LL, RR, LR, RL）进行旋转。
   • LL: 右旋
   • RR: 左旋
   • LR: 先左旋左孩子，再右旋根
   • RL: 先右旋右孩子，再左旋根

代码实现

文件名称: avl_tree_impl.py

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def get_height(self, node):
        if not node:
            return 0
        return node.height
    
    def get_balance(self, node):
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)
    
    def rotate_right(self, y):
        """右旋 (LL情况)"""
        x = y.left
        T2 = x.right
        
        # 执行旋转
        x.right = y
        y.left = T2
        
        # 更新高度
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        
        return x # 新的根
    
    def rotate_left(self, x):
        """左旋 (RR情况)"""
        y = x.right
        T2 = y.left
        
        y.left = x
        x.right = T2
        
        x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
        
        return y

    def insert(self, root, key):
        # 1. 标准BST插入
        if not root:
            return AVLNode(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)
        
        # 2. 更新高度
        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
        
        # 3. 获取平衡因子
        balance = self.get_balance(root)
        
        # 4. 如果不平衡，执行旋转
        
        # Case 1: LL
        if balance > 1 and key < root.left.key:
            return self.rotate_right(root)
        
        # Case 2: RR
        if balance < -1 and key > root.right.key:
            return self.rotate_left(root)
        
        # Case 3: LR
        if balance > 1 and key > root.left.key:
            root.left = self.rotate_left(root.left)
            return self.rotate_right(root)
        
        # Case 4: RL
        if balance < -1 and key < root.right.key:
            root.right = self.rotate_right(root.right)
            return self.rotate_left(root)
        
        return root

# 测试演练
if __name__ == "__main__":
    tree = AVLTree()
    root = None
    # 插入会导致不平衡的序列
    for val in [10, 20, 30, 40, 50, 25]:
        root = tree.insert(root, val)
    
    print(f"根节点: {root.key}, 高度: {root.height}, 平衡因子: {tree.get_balance(root)}")
    # 预期根节点会根据旋转变化，保持平衡

第七部分：红黑树（Red-Black Tree）

算法思想基础

红黑树是一种自平衡二叉查找树，但它通过给节点着色（红/黑）并遵循五条规则来保证平衡。相比AVL树，红黑树的旋转次数更少，因此在插入/删除频繁的场景（如C++ STL map, Java TreeMap, Python dict 早期版本的部分底层逻辑参考）中性能更优。

• 特性：从根到叶子的最长路径不超过最短路径的2倍。
• 复杂度：O(log n)。

题目 8：红黑树的节点定义与颜色翻转

题目描述：由于红黑树完整实现代码量巨大（涉及复杂的Case讨论），本题要求实现红黑树的节点结构，并模拟一次简单的“左旋”和“颜色翻转”操作，这是红黑树插入修复的核心步骤。

算法分析

红黑树插入修复主要依赖：

1. 变色：改变节点颜色。
2. 旋转：左旋或右旋调整结构。
   本题演示这两个基本原子操作，它们是构建完整红黑树的基石。

代码实现

文件名称: rbt_core_ops.py

class Color:
    RED = True
    BLACK = False

class RBNode:
    def __init__(self, key, color=Color.RED):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None # 红黑树通常需要父指针方便向上回溯

class RedBlackTreeOps:
    @staticmethod
    def rotate_left(node):
        """
        左旋操作示意
        返回新的根节点
        """
        if not node or not node.right:
            return node
        
        right_child = node.right
        node.right = right_child.left
        if node.right:
            node.right.parent = node
            
        right_child.left = node
        right_child.parent = node.parent
        node.parent = right_child
        
        # 颜色交换通常在旋转后根据具体Case处理，这里仅做结构旋转
        return right_child

    @staticmethod
    def flip_colors(node):
        """
        颜色翻转：当前节点变红，左右孩子变黑
        常用于2-3树向红黑树转换的逻辑模拟
        """
        if not node:
            return
        node.color = Color.RED
        if node.left:
            node.left.color = Color.BLACK
        if node.right:
            node.right.color = Color.BLACK

# 测试演练
if __name__ == "__main__":
    # 构建一个简单的局部结构进行测试
    root = RBNode(10, Color.BLACK)
    root.right = RBNode(20, Color.RED)
    root.right.parent = root
    
    print(f"旋转前根: {root.key}, 右孩子: {root.right.key}")
    
    ops = RedBlackTreeOps()
    new_root = ops.rotate_left(root)
    
    print(f"旋转后根: {new_root.key}, 左孩子: {new_root.left.key}")
    
    ops.flip_colors(new_root)
    print(f"翻转后根颜色: {'红' if new_root.color else '黑'}, 左孩子颜色: {'红' if new_root.left.color else '黑'}")

题目 9：验证红黑树性质

题目描述：给定一个已构建好的红黑树结构（节点包含颜色和左右指针），编写函数验证其是否满足红黑树的5条基本性质。

算法分析

需要验证：

1. 节点是红或黑。
2. 根是黑。
3. 叶子（NIL）是黑（代码中通常用None表示，隐含为黑）。
4. 红节点的子节点必须是黑（不能有连续红节点）。
5. 从任一节点到其所有后代叶子的路径包含相同数量的黑节点（黑高一致）。

代码实现

文件名称: verify_rbt.py

def verify_rbt_properties(root):
    """
    验证红黑树性质
    返回 (is_valid, black_height)
    """
    if not root:
        return True, 1 # 空树视为有效，黑高为1 (包含NIL)
    
    # 性质2: 根必须是黑色
    if root.color: # True is RED
        return False, 0
    
    def check_no_consecutive_reds(node):
        if not node:
            return True
        if node.color: # Node is Red
            if (node.left and node.left.color) or (node.right and node.right.color):
                return False
        return check_no_consecutive_reds(node.left) and check_no_consecutive_reds(node.right)
    
    def get_black_height(node):
        if not node:
            return 1
        left_bh = get_black_height(node.left)
        right_bh = get_black_height(node.right)
        
        if left_bh == -1 or right_bh == -1 or left_bh != right_bh:
            return -1
        
        return left_bh + (0 if node.color else 1)
    
    # 检查性质4
    if not check_no_consecutive_reds(root):
        return False, 0
    
    # 检查性质5
    bh = get_black_height(root)
    if bh == -1:
        return False, 0
        
    return True, bh

# 模拟一个合法的红黑树片段进行测试
if __name__ == "__main__":
    # 构造: Black(10) -> Left: Red(5), Right: Red(15)
    root = RBNode(10, Color.BLACK)
    root.left = RBNode(5, Color.RED)
    root.right = RBNode(15, Color.RED)
    
    valid, bh = verify_rbt_properties(root)
    print(f"树是否有效: {valid}, 黑高: {bh}")
    
    # 破坏性质：让根变红
    root.color = Color.RED
    valid, bh = verify_rbt_properties(root)
    print(f"根变红后是否有效: {valid}")

第八部分：综合应用

题目 10：前 K 个高频元素（混合查找策略）

题目描述：给定一个整数数组 nums 和一个整数 k，返回出现频率最高的 k 个元素。要求时间复杂度优于 O(n log n)。

算法分析

这道题综合了哈希查找和堆/排序的思想。

1. 使用哈希表（Hash Map）统计频率：O(n)。
2. 维护一个大小为 k 的最小堆，或者对频率进行快速选择（Quick Select，基于分区思想的查找）。
   这里展示使用哈希统计 + 桶排序（Bucket Sort，一种特殊的查找分发）的方法，可以达到 O(n)。

代码实现

文件名称: top_k_frequent.py

from collections import defaultdict

def top_k_frequent(nums, k):
    """
    使用哈希统计 + 桶排序思想查找前K个高频元素
    :param nums: List[int]
    :param k: int
    :return: List[int]
    """
    # 1. 哈希查找统计频率 O(N)
    count_map = defaultdict(int)
    max_freq = 0
    for num in nums:
        count_map[num] += 1
        max_freq = max(max_freq, count_map[num])
    
    # 2. 桶排序：索引代表频率，值为该频率下的数字列表
    # 频率范围是 1 到 max_freq
    buckets = [[] for _ in range(max_freq + 1)]
    
    for num, freq in count_map.items():
        buckets[freq].append(num)
    
    # 3. 从高频率桶开始收集结果
    result = []
    for i in range(max_freq, 0, -1):
        if buckets[i]:
            result.extend(buckets[i])
            if len(result) >= k:
                return result[:k]
    
    return result

# 测试演练
if __name__ == "__main__":
    data = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4]
    k = 2
    print(f"前 {k} 个高频元素: {top_k_frequent(data, k)}")
    # 预期输出: [3, 1] (顺序可能不同，取决于桶内顺序)

小结

本文通过10道算法题，系统地梳理了Python中的查找算法体系：

1. 线性查找：简单直接，适用于小规模或无序数据。
2. 二分及其变种：利用有序性将效率提升至对数级，是面试和工程中的常客。
3. 插值与斐波那契：针对特定数据分布的优化策略。
4. 哈希查找：以空间换时间的极致，实现了 O(1) 的平均查找速度。
5. 树形查找（BST, AVL, RBT）：解决了动态数据集的有序查找问题。其中AVL追求严格平衡，适合读多写少；红黑树通过放宽平衡条件减少旋转，适合读写频繁的场景（如语言标准库的实现）。