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

作者 张鏖烽单位 湖南工程学院计算机与通信学院编程实现线性表的折半查找算法函数HalfSearch(L,k):在线性表L中折半查找关键字k查找成功返回其逻辑位序否则返回0 同时输出查找过程中依次与之比较的关键字注意顺序表L中的元素是有序的。函数接口定义在这里描述函数接口。例如 int HalfSearch(SqList *L,int k);其中L为顺序表k为待查找关键字裁判测试程序样例在这里给出函数被调用进行测试的例子。例如 #includestdio.h #includemalloc.h #define MaxSize 100 typedef struct{ int data[MaxSize]; int length; }SqList; void InitList(SqList *L) { L(SqList *)malloc(sizeof(SqList)); L-length0; } int HalfSearch(SqList *L,int k);//折半查找算法 int main() { int k,i,n; SqList *L; InitList(L); scanf(%d,n); for(i0;in;i) scanf(%d,L-data[i]); L-lengthn; scanf(%d,k); printf(折半查找关键字%d需要依次比较,k); iHalfSearch(L,k); if(i0) printf(\n关键字%d查找失败,k); else printf(\n关键字%d是线性表中第%d个元素,k,i); return 0; } /* 请在这里填写答案 */输入样例在这里给出一组输入。例如第1行关键字个数第2行关键字序列第3行待查找关键字k9 1 4 6 9 12 23 25 30 45 30输出样例在这里给出相应的输出。例如折半查找关键字30需要依次比较12 25 30 关键字30是线性表中第8个元素参考代码int HalfSearch(SqList *L,int k) { int low0,highL-length-1,mid; while(lowhigh){ mid(lowhigh)/2; printf(%d ,L-data[mid]); if (L-data[mid]k) return mid1; else if (L-data[mid]k) lowmid1; else highmid-1; } return 0; }