供自己或有需要的朋友查询参考。

博客内容为自我总结而来，所以描述皆按本人理解，如有错误请帮忙指出来谢谢。

 

1.顺序查找（线形查找）

//a[]为要查询的表，key为要查询的值，n表示查询表内元素的个数
int SequenceSearch(int a[], int key, int n)｛
    for(int i = 0; i < n; ++i){
        if(a[i] == key){
 
            return i;
        }
    }
    return -1;
｝

2.二分查找（折半查找）

//a[]为要查询的表，key为要查询的值，n表示查询表内元素的个数
int BinarySearch(int a[], int key, int n){
    int low, high, mid;
    low = 0;                     
    high = n - 1;                
    while( low <= high ){
        mid = (low + high)/2;    //二分 表
        if( a[mid] == key ){
            return mid;
        }
        if( a[mid] > key ){
            high = mid - 1;      //重新设置查找范围[low,mid-1]
        }
        if( a[mid] < key){
            low = mid + 1;       //重新设置查找范围[mid+1,high]
        }
    }
    return -1;
}

3.插值查询

属于有序查找算法，基于二分查找。

适用：表长较大，关键字分布又比较均匀的查找表。

时间复杂度：O(log2(log2n))。

关键 mid = low+(key-a[low])/(a[high]-a[low])*(high-low)

使用代码来理解

//a[]为要查询的表，key为要查询的值，low最小下标，high最大下标
int InsertialSearch(int a[], int key, int low, int high){
    int mid;
    while(low <= hight){
        mid = low+(key-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid] ==key){
            return mid;
        }
        if(a[mid] > key){
            high = mid - 1;   //将范围设置为[low,mid-1]
        }
        if(a[mid] < key){
            low = mid + 1;    //将范围设置为[mid+1,high]
        }
    }
    return -1;
}