思考

本质是什么？在一堆数据中查找一个或少数个数据
限制条件是什么？数据量、存储位置、是否有序。查找需要CPU在内存上操作，数据的存储（内存，磁盘），数据量太大时无法将数据一次性加载到内存
存在哪些算法？复杂度是多少？
代码如何实现？

类型

顺序查找

基本思想

从前往后扫描比较

算法描述

遍历整个数组，一个for循环即可

算法分析

时间复杂度：查找算法 - 图1
空间复杂度：查找算法 - 图2
无需额外内存空间

代码实现

int SequentialSearch(int arr[], int length, int key) {
    int i;
    for (i = 0; i < length; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

适用场景

无序
数据量小

二分查找

基本思想

先保证数据有序，如从小到大

算法描述

先将数据排序
查找选择点： $查找算法 - 图3$ %20%2F%202#card=math&code=mid%20%3D%20low%20%2B%C2%A0%28high%20-%20low%29%20%2F%202&id=Nr5IE)
若小于关键字则在前部分查找，若大于关键字则在后部分查找
重复第2、3步

算法分析
时间复杂度：
空间复杂度：

代码实现

适用场景
有序
数据量小

插值查找

基本思想
基于二分查找，查找选择点由正中间点变为自适应点即选择离更近的一方

算法描述
查找选择点： $查找算法 - 图6$ %20*%20(key%20-%20arr%5Blow%5D)%20%2F%20(arr%5Bhigh%5D%20-%20arr%5Blow%5D)#card=math&code=mid%20%3D%20low%20%2B%20%28high%20-%20low%29%20%2A%20%28key%20-%20arr%5Blow%5D%29%20%2F%20%28arr%5Bhigh%5D%20-%20arr%5Blow%5D%29&id=kfoHb)

算法分析
时间复杂度：
空间复杂度：

代码实现

适用场景
有序
数据量小
分布均匀

斐波那契查找

基本思想
基于二分查找，查找选择点为斐波那契数列

算法描述
查找选择点：

复杂度
时间复杂度：
空间复杂度：

适用场景
有序
数据量小

分块查找（索引顺序查找）

基本思想
基于顺序查找，先将数据分块，块内结点无需有序，但块与块间必须有序（块1中所有元素均小于块2任一元素）

算法描述
选择每块最大关键字作索引表
先对索引表作顺序查找/二分查找，再在确定块内进行顺序查找
算法分析
时间复杂度：
空间复杂度：
适用场景
有序
数据量小
树表查找
二叉搜索树、红黑树、B树、B+树
基本都可以算是二分查找的变种
二叉树查找