第十四周项目1-验证算法（1-折半查找算法）

问题及代码：

/* copyright （t） 2016，烟台大学计算机学院 *All rights reserved. *文件名称：1.cpp *作者：常锐 *完成日期：2016年12月2日 *版本号：v1.0 *问题描述：认真阅读并验证折半查找算法。请用有序表{12,18,24,35,47,50,62,83,90,115,134}作为测试序列，分别对查找90、47、100进行测试。 *输入描述：无 *程序输出：测试结果 */

#include <stdio.h> #define MAXL 1000 //定义顺序表中最大元素个数为1000 typedef int KeyType; typedef int InfoType; typedef struct { KeyType key; } NodeType; typedef NodeType SeqList[MAXL]; //定义顺序表类型 int BinSearch(SeqList R,int n,KeyType x) { int low=0,high=n-1; int mid; while(low<=high) { mid=(low+high)/2; if(R[mid].key==x) return mid+1; //查找成功，返回逻辑序号mid+1 if(R[mid].key<x) low=mid+1; //区间减半，在后半区间继续查找 if(R[mid].key>x) high=mid-1; //区间减半，在前半区间继续查找 } return 0; //查找不成功时，返回0 } int main() { int i,n=10; int x,result; SeqList R; KeyType a[]= {12,18,24,35,47,50,62,83,90,115,134}; while(scanf("%d",&x)!=EOF) { for (i=0; i<n; i++) R[i].key=a[i]; result = BinSearch(R,n,x); if(result>0) printf("序列中第 %d 个是 %d\n",result, x); else printf("木有找到！\n"); } return 0; }

运行结果：

知识点总结：

        线性表的折半查找

心得体会：

        折半查找算法针对数据量较大的情形，效率较高；但只能用顺序方式存储。此外，折半查找还可用递归的方法实现。