七大查找算法

1 顺序查找

//顺序查找
int SequenceSearch(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i] == value)
            return i;
    return -1;
}

2 二分查找

//二分查找（折半查找），版本1
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

3 插值查找(二分法的改进)

　　在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？
　　打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。
　　同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。
　　经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下：
　　mid=(low+high)/2, 即mid=low+1/2(high-low);
　　通过类比，我们可以将查找的点改进为如下：
　　mid=low+(key-a[low])/(a[high]-a[low])(high-low)，
　　也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。
　　基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
　　注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。
　　复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}

4 斐波那契查找(二分法的改进)

int mid=low+F[k-1]-1;

#include <cstring>
#include <iostream>
using namespace std;

const int max_size=20; //斐波那契数组的长度
/*构造一个斐波那契数组*/
void Fibonacci(int * F){
    F[0]=0;
    F[1]=1;
    for(int i=2;i<max_size;++i)
        F[i]=F[i-1]+F[i-2];
}

/*定义斐波那契查找法*/
//a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
int FibonacciSearch(int *a, int n, int key){
    int low=0;
    int high=n-1;
    int F[max_size];
    Fibonacci(F);//构造一个斐波那契数组F
    int k=0;
    while(n>F[k]-1)//计算n位于斐波那契数列的位置
        ++k;

    int *temp;//将数组a扩展到F[k]-1的长度
    temp=new int [F[k]-1];
    memcpy(temp, a, n*sizeof(int));
    for(int i=n;i<F[k]-1;++i)
        temp[i]=a[n-1];

    while(low<=high){
        int mid=low+F[k-1]-1;
        if(key<temp[mid]){
            high=mid-1;
            k-=1;
        }
        else if(key>temp[mid]){
            low=mid+1;
            k-=2;
        }
        else{
            if(mid<n)
                return mid; //若相等则说明mid即为查找到的位置
            else
                return n-1; //若mid>=n则说明是扩展的数值,返回n-1
        }
    }
    delete []temp;
    return -1;
}

void test(){
    int a[] = {0,16,24,35,47,59,62,73,88,99};
    int key = 100;
    int index = FibonacciSearch(a, sizeof(a)/sizeof(int), key);
    cout << key << " is located at: " << index << endl;
}

int main(){
    test();
    return 0;
}

5 树表查找（比较难，文件系统）

二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。
基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。

6 分块查找（类似字典）

　　分块查找又称索引顺序查找，它是顺序查找的一种改进方法。
　　算法思想：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2 块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……
　　算法流程：
　　step1 先选取各块中的最大关键字构成一个索引表；
　　step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找

7 哈希查找（以空间换时间 的算法）

哈希查找，又称哈希搜索，是一种通过哈希表来进行查找的数据结构算法。哈希表（Hash table）是一种用于快速查找的数据结构，它通过哈希函数将关键字映射到表的一个位置上，以便进行快速查找。

算法思路：
1、先将序列映射到hash表中
2、查找时，先找到对应的hash表，然后顺序查找

参考文件

https://www.cnblogs.com/maybe2030/p/4715035.html#top