查找（Search）

一、查找的第一性原理

查找的本质不是“比较”，而是：

在给定约束条件下，用尽可能低的成本，缩小目标的不确定性空间。

所有查找结构，本质上都在回答三个问题：

  1. **不确定性如何被缩小？**
  2. **缩小的代价是什么？**
  3. **这种代价是否可以被接受？**

因此，查找问题的核心权衡只有四个维度：

二、查找问题的整体知识结构

查找（Search）问题体系├── 一、确定性查找（精确定位）│   ├── 顺序查找（无结构）│   ├── 二分查找（有序 + 随机访问）│├── 二、空间换时间的直接映射│   ├── Bitmap│   ├── Hash 映射│├── 三、概率型存在性查找│   ├── 布隆过滤器│   ├── 布谷鸟过滤器│├── 四、时间维度上的查找（调度索引）│   ├── 单层时间轮│   ├── 分层时间轮│└── 五、工程级抽象：索引    ├── 索引的本质    ├── 选型约束与权衡

三、确定性查找：用结构消除不确定性

1. 顺序查找（Linear Search）

本质原理

不确定性收敛速度

int seq_search(int array[], int n, int key){    for(int i = 0; i < n; i++)    {        if(key == array[i])            return i;    }    return -1;}

工程哲学

2. 二分查找（Binary Search）

本质原理

二分查找不是“技巧”，而是利用全序关系进行信息熵减半。

每一次比较，都会排除 一半的可能性空间。

二分查找

int l = 0, r = a.length - 1;while (l <= r) {    int mid = l + (r - l) / 2;    if (a[mid].equals(target)) {        return mid;    }    if (less(target, a[mid])) {        r = mid - 1;    } else {        l = mid + 1;    }}return -1;

隐含约束（本质代价）

工程迁移能力

二分查找是一种问题拆解思维：不仅用于数据查找，也用于：

四、空间换时间：用存储消除计算

1. Bitmap（位图）

本质原理

用空间换取 O(1) 的存在性判断。

1存在 => 0100002存在 => 0010001,2都存在 => 011000

本质代价

五、概率型查找：允许错误以换取极致效率

1. 布隆过滤器（Bloom Filter）

布隆过滤器

本质原理

用多重哈希 + 位图判断“是否可能存在”。

关键权衡

工程哲学

布隆过滤器的真正价值在于：提前否定不可能发生的请求。

2. 布谷鸟过滤器（Cuckoo Filter）

2022817204730

本质原理

相比布隆过滤器的演进

六、时间维度的查找：时间轮

时间轮本质不是“定时器”，而是在时间轴上建立索引结构。

1. 单层时间轮（Round）

2022616155327

本质思想

round 的意义

用“圈数”表示未来的距离，将无限时间映射为有限结构。

2. 分层时间轮

2022616155817

本质演进

本质类比

分层时间轮 ≈时间维度上的 B+ 树

七、工程级抽象：索引（Index）

1. 索引的本质

索引不是数据结构，而是 “查找约束下的组织方式”。

2. 功能性约束

3. 非功能性约束

4. 常见索引结构（按思想分类）

思想结构
映射Hash
有序红黑树 / B+ 树
跳跃跳表
否定布隆过滤器

八、查找结构的演进总览

线性扫描→ 有序结构（二分 / 树）→ 映射定位（Hash / Bitmap）→ 概率容错（Bloom / Cuckoo）→ 维度扩展（时间轮）→ 系统级索引

九、总结：查找不是算法，而是认知方式

所有查找结构，都是对"不确定性"的不同妥协方式。

关联内容（自动生成）