PTA 查找算法设计 1 线性表折半查找

作者 张鏖烽

单位 湖南工程学院计算机与通信学院

编程实现线性表的折半查找算法函数：

HalfSearch(L,k):在线性表L中折半查找关键字k，查找成功返回其逻辑位序，否则返回0 ，同时输出查找过程中依次与之比较的关键字

注意：顺序表L中的元素是有序的。

函数接口定义：

在这里描述函数接口。例如： int HalfSearch(SqList *L,int k);

其中L为顺序表，k为待查找关键字；

裁判测试程序样例：

在这里给出函数被调用进行测试的例子。例如： #include<stdio.h> #include<malloc.h> #define MaxSize 100 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList *&L) { L=(SqList *)malloc(sizeof(SqList)); L->length=0; } int HalfSearch(SqList *L,int k);//折半查找算法 int main() { int k,i,n; SqList *L; InitList(L); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&L->data[i]); L->length=n; scanf("%d",&k); printf("折半查找关键字%d需要依次比较：",k); i=HalfSearch(L,k); if(i==0) printf("\n关键字%d查找失败！",k); else printf("\n关键字%d是线性表中第%d个元素！",k,i); return 0; } /* 请在这里填写答案 */

输入样例：

在这里给出一组输入。例如：

第1行：关键字个数

第2行：关键字序列

第3行：待查找关键字k

9 1 4 6 9 12 23 25 30 45 30

输出样例：

在这里给出相应的输出。例如：

折半查找关键字30需要依次比较：12 25 30 关键字30是线性表中第8个元素！

参考代码：

int HalfSearch(SqList *L,int k) { int low=0,high=L->length-1,mid; while(low<=high){ mid=(low+high)/2; printf("%d ",L->data[mid]); if (L->data[mid]==k) return mid+1; else if (L->data[mid]<k) low=mid+1; else high=mid-1; } return 0; }