跳到主要内容

搜索策略

为什么搜索很重要​

搜索是数据访问和检索的核心基础：

  • 数据库查询：寻找符合特定条件的记录。
  • 文件系统：通过名称或内容定位文件。
  • 网页搜索：在海量互联网数据中发现相关页面。
  • API 接口：对集合数据进行过滤和检索。

实际影响：

  • 在 10 亿个元素中进行二分查找：仅需约 30 次比较。
  • 线性搜索：平均需要 5 亿次比较。
  • 效率提升 1600 万倍。

核心概念​

搜索算法对比​

算法时间复杂度前提条件最适合场景
线性搜索O(n)无无序数据、小型数组
二分查找O(log n)有序数组大型有序数据集
插值搜索平均 O(log log n)均匀分布的有序数组数值型、均匀分布的数据
指数搜索O(log n)无界/无限大的有序数组长度未知、流式数据

二分查找复习​

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right) {
        // 防止 (left + right) / 2 导致的整型溢出
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

深入理解​

原理：根据目标值在已知范围内的位置进行“智能估算”。类似于你在字典中找“Zoo”会直接翻到最后几页，而不是从中间开始。

最佳情况：对于均匀分布的数据可达 O(1)。 最差情况：数据分布极度不均时退化为 O(n)。

适用场景：数组大小未知或无限大。 策略：先通过倍增步长 (1, 2, 4, 8...) 确定目标所在的范围，再在该范围内执行标准二分查找。

在行和列均有序的 2D 矩阵中查找：

策略：从右上角开始。

  • 若当前值 > 目标：向左移（列减 1）。
  • 若当前值 < 目标：向下移（行加 1）。 时间复杂度：O(m + n)，其中 m 为行数，n 为列数。

实战应用​

搜索旋转排序数组​

核心：即使数组被旋转了，其中一半依然是有序的。利用这一特性，每次排除掉不可能的一半。

搜索插入位置​

核心：二分查找的变体。当找不到目标值时，返回 left 指针的位置即为应插入的索引。

面试高频题​

Q1: 既然二分查找这么快，为什么不一直用它？​

回答：二分查找有两个硬性开销：

  1. 必须有序：排序本身通常需要 O(n log n)。
  2. 随机访问：需要支持 O(1) 随机访问（如数组）。在链表上执行二分查找由于寻址开销，效率并不高。

Q2: 如何在不知道长度的有序流中查找数据？​

回答：使用指数搜索 (Exponential Search)。首先检查索引 0, 1, 2, 4, 8... 找到第一个大于目标值的索引，确定边界后在 [i/2, i] 区间内进行二分查找。

延伸阅读​

  • 二分查找变体：查找第一个/最后一个出现的元素。
  • 双指针技术：常与搜索策略结合使用。
  • 树结构搜索：理解 BST 和 B+ 树的查找逻辑。
  • LeetCode：搜索标签题目