定义

查找(Searching)：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。
查找表(Search Table)是由同一类型的数据元素(记录)构成的集合。
关键字(Key)是数据元素中某个数据项的值，⼜又称为键值。 ⽤用它可 以表示⼀个数据元素，也可以标识一个记录的某个数据项(字段)。我们称为关键码。
若关键字可以唯⼀地标识⼀个记录，则称此关键字为主关键字 (Primary Key)
对于那些可以识别多个属于元素(记录)的关键字，我们称为次关键字(Secondary Key)

静态查找和动态查找

• 静态查找：只做查找操作的查找表。

1. 查询某个“特定”数据元素是否在查找表中。
2. 检索某个“特定”数据元素和各种属性。

• 动态查找：在查找的过程中，同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

1. 查找时插入数据元素。
2. 查找时删除数据元素。

顺序表查找

顺序查找(Sequential Search)，⼜称为线性查找。是最基本的查找技术。它的查找过程：从表中的第一个(或最后一个)记录开始，逐个进⾏记录关键字和给定值⽐较；

1. 若某个记录的关键字和给定值相等，则查找成功，找到所查记录。
2. 如果直到最后一个(或第⼀个)记录，其关键字和给定值⽐较都不等 时，则表中没有所查的记录，查找不不成功。

代码实现

//1.顺序查找
//a为数组,n为查找的数组个数,key为要查找的关键字;
int Sequential_Search(int *a,int n,int key){
    for(int i = 1; i<=n; i++){//预留哨兵的位置a[0]
        if(a[i] == key){
            return i;
        }
    }
    return 0;
}
//2.顺序查找_哨兵，此方法较上面方法的优势是，减少了每次越界的检查
int Sequential_Search2(int *a,int n,int key){
    a[0] = key;
    int i = n;
    while(a[i] != key){
        i--;
    }
    return i;
}

有序列查找

折半查找

折半查找(Binary Search)技术，⼜称为⼆分查找。它的前提是线性表中的记录必须是关键码有序(通常是从小到大有序)，线性表必须采用顺序存储。
折半查找的基本思想是：
在有序表中，取中间记录作为⽐较对象，

1. 若给定值与中间记录的关键字相等则查找成功。
2. 若给定值小于中间记录的关键字，则在中间记录的左半区继续查找。
3. 若给定值⼤于中间记录的关键字，则在中间记录的右半区继续查找。
4. 不断重复以上的过程，直到查找成功。或所以查找区域无记录，查找失败为止。

折半查找代码实现

//3.折半查找算法
//假设数组a,已经是有序的(从小到大)
int Binary_Search(int *a,int n,int key){
    int low = 1;
    int high = n;
    int mid;
    while(low<=high){
        mid = (low + high) /2;
        if(a[mid]>key){
            high = mid-1;
        }
        else if(a[mid]<key){
            low = mid+1;
        }
        else
            return mid;
    }
    return 0;
}

插值查找

插值查找(Interpolation Search):是根据查找的关键字key 与查找表中最大最⼩记录的关键字⽐较后的查找⽅法，其核⼼就是在于插值的计算公式:

image.png
插值查找为折半查找的一种优化方案，适用于有序序列均匀分布的情况。

插值查找代码实现

//4. 插值查找
int Interpolation_Search(int *a,int n,int key){
    int low = 1;
    int high = n;
    int mid;
    while(low<=high){
        //当前key大概分布的范围，这种排序要求也是有序且，且数据排列均匀分布
        float rate = (key-a[low])/(a[high]-a[low]);
        mid = low+rate*(high-low);
        if(a[mid]>key){
            high = mid-1;
        }
        else if(a[mid]<key){
            low = mid+1;
        }
        else
            return mid;
    }
    return 0;
}

斐波拉契查找

斐波拉契查找利用了黄金分割的原理来实现。

斐波拉契查找代码实现

//5.斐波拉契查找
int F[100]; /* 斐波那契数列 */
int Fibonacci_Search(int *a,int n,int key){
    F[0]=0;
    F[1]=1;
    for(int i = 2; i<100;i++){
        F[i] = F[i-1]+F[i-2];
    }
    int mid;
    int low = 1,high = n;
    int k = 0;
    //计算n位于斐波拉契序列中的大概位置
    while(n>F[k]-1){
        k++;
    }
    for(int i = n; i<F[k]-1; i++){
        a[i] = a[n];
    }
    
    while(low<=high){
        mid = low+F[k-1]-1;//计算当前分隔点的下标
        if(a[mid]>key){
            high = mid-1;
            k = k-1;
        }
        else if(a[mid]<key){
            low = mid+1;
            k = k-2;
        }
        else{
            if(mid <= n){
                return mid;
            }
            else{
                return n;
            }
        }
    }
    return 0;
}

斐波拉契算法核心

1. 当key = a[mid]时，查找就成功。
2. 当key < a[mid]时，新范围就是第low个到第mid-1个。此时范围个数为F[K-1]。
3. 当key > a[mid]时，新范围就是第mid+1个到第high个。此时范围个数为F[K-2]-1。