顺序查找

普通的顺序查找

//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;
}

顺序查找-使用a[0] 哨兵 减少了越界判断

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;
}

折半查找算法 二分查找法

先排序 再查找 适用于有序的数据

//假设数组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;
}

基于折半查找的优化 —— 插值查找

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;
}

斐波拉契查找

int F[100]; /* 斐波那契数列 */
int Fibonacci_Search(int *a,int n,int key){
  
    int low,high,mid,i,k;
    //最低下标为记录的首位;
    low = 1;
    //最高下标为记录的末位;
    high = n;
    k = 0;
    
    //1.计算n为斐波拉契数列的位置;
    while (n > F[k]-1) {
        k++;
    }
    
    //2.将数组a不满的位置补全值;
    for(i = n;i < F[k]-1;i++)
        a[i] = a[n];
    
    //3.
    while (low <= high) {
        
        //计算当前分隔的下标;
        mid = low+F[k-1]-1;
        
        
        if (key < a[mid]) {
            //若查找的记录小于当前分隔记录;
            //将最高下标调整到分隔下标mid-1处;
            high = mid-1;
            //斐波拉契数列下标减1位;
            k = k-1;
            
        }else if(key > a[mid]){
            //若查找的记录大于当前的分隔记录;
            //最低下标调整到分隔下标mid+1处
            low = mid+1;
            //斐波拉契数列下标减2位;
            k = k-2;
            
        }else{
            if (mid <= n) {
                //若相等则说明,mid即为查找的位置;
                return mid;
            }else
            {
                //若mid>n,说明是补全数值,返回n;
                return n;
            }
        }
    }
    return 0;
}