数据结构之查找1

查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找表是由同一个类型的数据元素（或记录）的集合。

关键字是数据元素中某个数据项的值。

若次关键字可以唯一的标识一个记录，则称次关键字为主关键字。

对于识别多个数据元素（或记录）的关键字，称为次关键字。

静态查找表：只做查找操作的查找表。主要操作：查找某个特定的元素是否在表中，检索特定的数据元素和各种属性。

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

顺序查找也叫线性查找，是基本的查找技术，它的查找过程：从表中的第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录和给定的关键值相等，则查找成功，找到所查找的记录，若到最后一个（或第一个）元素其关键字和给定值都不相等，则查找失败，没有找到查找元素。

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

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

}

时间复杂度O(n)，平均查找次数（n+1)/2

折半查找又称二分查找，它的前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功，若小于给定中间记录的关键字，则在中间记录的左半区继续查找，若给定值大于中间记录的关键字，则在中间记录的右半区继续查找，不断的重复以上操作，直到查找成功，或查找区域无记录，查找记录失败。

插值插值是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就是在于插值的计算公式：(key-a[low])/(a[high]-a[low])。时间复杂度O(logn)

斐波那契查找：

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