欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构23————有序表查找

程序员文章站 2024-03-19 19:09:34
...

数据结构23————有序表查找

一. 目录

二. 有序表查找

有序表查找即在一个有序表中查找需要的值,因为是有序的所以可以不用如线性表那样遍历所有数据,可以利用有序这一特点进行查找。

三. 二分(折半)查找

1. 思路

在有序表(从小到大)中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功,如给定值小于中间记录的关键字,则在中间记录的左半区继续查找,若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。

2.代码

#include <stdio.h>
//二分查找, a为查找的数组(数组从1开始存储),n为数组长度,key为要查找的关键字
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]){
            high = mid-1;
        }else if(key == a[mid]){
            return mid;
        }else if(key > a[mid]){
            low = mid+1;
        }
    }
    return 0;
}

3.时间复杂度

对于一个有n个数据有序数组,最好的情况下查找次数:1次,最坏的情况下查找次数[log2n]+1, 所以二分查找的时间复杂度为O[logn]

四. 插值查找

1.产生原因

在有些时候,二分查找时每次和最中间的相比,并不是最优的情况,比如说在均匀分布1-100的有序数组中查找5,我们自然会考虑从下标比较小的开始查找。所以在这种情况下,二分查找依然有改进的空间

2.思路

插值查找是根据要查找的关键字key和查找表中的最大最小记录的关键字比较后的查找方法,其核心公式是keya[low]a[high]a[low],即每次将给定值与下标为keya[low]a[high]a[low]的值进行比较

3.代码

总体和二分查找差不多,不过将mid = (low+high)/2改为:mid = low +(high - low)*(key-a[low])/(a[high]-a[low])

五. 斐波那契查找

对于二分查找的改进除了插值查找外,还有一种,即斐波那契查找。

1.思路

斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,即n=Fk-1(不足补齐) , F(K)为斐波那契数列。即{0,1,1,2,3,5,8,13……}
核心思路:
开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种:
1. 相等,mid位置的元素即为所求
2. 大于 ,low=mid+1,k-=2; 即:查找的元素在[mid+1,hign]范围内,元素个数为F(k-2)-1个
3. 小于,high=mid-1,k-=1; 即:查找的元素在[[low,mid-1]]范围内,元素个数为F(k-2)-1个
数据结构23————有序表查找

2.代码

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; //若相等则说明mid即为查找到的位置 
            }else{
                return n; // 若mid>n说明是补全数组,返回n 
            }
        } 
    }
    return 0;
}

3.性能优越

关于斐波那契查找, 如果要查找的记录在右侧,则左侧的数据都不用再判断了,不断反复进行下去,对处于当众的大部分数据,其工作效率要高一些。所以尽管斐波那契查找的时间复杂度也为O(logn),但就平均性能来说,斐波那契查找要优于折半查找。可惜如果是最坏的情况,比如这里key=1,那么始终都处于左侧在查找,则查找效率低于折半查找。

还有关键一点,折半查找是进行加法与除法运算的(mid=(low+high)/2),插值查找则进行更复杂的四则运算(mid = low + (high - low) * ((key - a[low]) / (a[high] - a[low]))),而斐波那契查找只进行最简单的加减法运算(mid = low + F[k-1] - 1),在海量数据的查找过程中,这种细微的差别可能会影响最终的效率。

六. 参考资料

《大话数据》
《数据结构与算法》