查找（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存在 => 010000
2存在 => 001000
1,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）
→ 维度扩展（时间轮）
→ 系统级索引

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

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

关联内容（自动生成）