/** 折半查找的适用条件：1，有序表，对于无序表，实现需要“预处理”
* 2，限于顺序存储结构，对于线性链表则无法有效地进行查找等操作。
* 折半查找的原理：确定要查找表的上界，下界，中间值，用给定的键值和中间值比较
* 若想等则返回成功；否则缩小范围，继续比较直至查找成功或者所比较区间大小小于0
* 为止（不存在要查找的键值） ，区间大小要小于0，才表明查找失败 **/
#include<stdlib.h>
//定义存储结构
typedef struct {//表中每一个记录的类型，当然还可以在结构中添加其他的键值;
int key;
//......key1,key2,....
}elemType;
typedef struct{
elemType* init;
int length;
}SSTable;
//建立一个有序表
int createSTable(SSTable* t, int len){
int i;
if(!(t->init = (elemType*) malloc(sizeof(elemType)*len)))
return -1;
t->length = len;
printf("输入有序表的序列值：\n");
for(i = 0; i < t->length; ++i)
scanf("%d",&t->init[i].key);
}
//在有序表中查找一个key
int BinarySearch(SSTable* t, int key)...{
int low = 0,high = t->length-1,mid;
while(low <= high)...{ //保证区间长度大于或者等于0 mid = (low+high)/2; if(t->init[mid].key == key) return mid; else if(t->init[mid].key < key) low = mid + 1; else high = mid -1;
} return -1; //未查找到key在表中的下标返回-1 
}//简单测试
int main(void){
int n,key;
SSTable t;
printf("输入要建立的有序表的长度：\n");
scanf("%d",&n);
createSTable(&t,n);
printf("输入要查找的键值key:\n");
scanf("%d",&key);
printf("键值key在表中的下标是：%d",BinarySearch(&t,key));
system("pause");
return 0;
}
/** 比较：和前面的顺序查找相比，对有序表进行折半查找在查找成功的前提下，对于任意的表长n,当n>50的时候，
* 其平均查找长度(ASL)近似为log(2)[n+1] -1,要比顺序查找的ASL（（n+1)/2)高效得多，但是顺序查找对于任意
* 次序的表都适合，而折半查找是必须针对有序表并且不是线性链表。对于无序表，采用折半查找之前，需要
* 排序，根据采用排序算法的不同，此时整个折半查找的时间复杂度需要考虑排序的时间，而不仅仅是折半查找的
* 时间复杂度。*/
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
