数据结构23————有序表查找
数据结构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次，最坏的情况下查找次数， 所以二分查找的时间复杂度为
四. 插值查找
1.产生原因
在有些时候，二分查找时每次和最中间的相比，并不是最优的情况，比如说在均匀分布1-100的有序数组中查找5，我们自然会考虑从下标比较小的开始查找。所以在这种情况下，二分查找依然有改进的空间
2.思路
插值查找是根据要查找的关键字key和查找表中的最大最小记录的关键字比较后的查找方法，其核心公式是,即每次将给定值与下标为的值进行比较
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个
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），在海量数据的查找过程中，这种细微的差别可能会影响最终的效率。
六. 参考资料
《大话数据》
《数据结构与算法》