数据结构与算法---查找

概念：

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

静态查找表(Static Search Table): 只作查找操作的查找表;

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

动态查找表(Dynamic Search Table): 在查找过程中同时插⼊入查找表中不不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作;

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

顺序查找(Sequential Search), 又称为线性查找. 是最基本的查找技术. 它的查找过程: 从表中的第一个(或最后⼀个)记录开始,逐个进行记录关键字和给定值比较;

1.若某个记录的关键字和给定值相等,则查找成功,找到所查记录;
2.如果直到最后一个(或第一个)记录, 其关键字和给定值比较都不等 时, 则表中没有所查的记录,查找不成功;
3.代码如下：

//a为数组,n为查找的数组个数,key为要查找的关键字;
int Sequential_Search(int *a,int n,int key){
    for (int i = 1; i <= n ; i++)
        if (a[i] == key)
            return i;
    return 0;
}

4.顺序查找优化如下：

//2.顺序查找_哨兵
int Sequential_Search2(int *a,int n,int key){
    int i;
    //设置a[0]为关键字值,称为'哨兵'
    a[0] = key;
    //循环从数组尾部开始
    i = n;
    while (a[i] != key) {
        i--;
    }
    //返回0,则说明查找失败
    return i;
}

折半查找算法---折半查找(Binary Search)技术,又称为二分查找

1.前提：线性表中的记录必须是关键码有序(通常是从小到⼤有序),线性表必须采用顺序存储；
2.折半查找的基本思想：

• 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相 等则查找成功；
• 若给定值小于中间的记录关键字,则在中间记录的左半区继续查找；
• 若给定的值大于中间记录的关键字,则在中间记录的右半区继续查找;
• 不断重复以上的过程,直到查找成功,或所以查找区域无记录,查找失败 为⽌.

3. 代码如下：

//假设数组a,已经是有序的(从小到大)
int Binary_Search(int *a,int n,int key){
    
    int low,high,mid;
    //定义最低下标为记录首位
    low = 1;
    //定义最高下标为记录末位
    high = n;
    while (low <= high) {
        
        //折半计算
        mid = (low + high) /2;
       
        if (key < a[mid]) {
            //若key比a[mid] 小,则将最高下标调整到中位下标小一位;
            high = mid-1;
        }else if(key > a[mid]){
             //若key比a[mid] 大,则将最低下标调整到中位下标大一位;
            low = mid+1;
        }else
            //若相等则说明mid即为查找到的位置;
            return mid;
    }
    
    return 0;
}

插值查找

1.代码如下：

int Interpolation_Search(int *a,int n,int key){
    int low,high,mid;
    low = 1;
    high = n;
    
    while (low <= high) {
        
        //插值
        mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
    
        if (key < a[mid]) {
            //若key比a[mid]插值小,则将最高下标调整到插值下标小一位;
            high = mid-1;
        }else if(key > a[mid]){
            //若key比a[mid]插值 大,则将最低下标调整到插值下标大一位;
            low = mid+1;
        }else
            //若相等则说明mid即为查找到的位置;
            return mid;
    }
    
    return 0;
}

斐波拉契查找(Fibonacci Search)

1.代码如下：