实验七、查找算法的实现
一、实验目的
掌握顺序和二分查找算法的基本思想及其实现方法。
二、实验要求
问题描述：对给定的任意数组（设其长度为n），分别用顺序和二分查找方法在此数组中查找与给定值k相等的元素。
顺序查找基本思想：从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。
二分查找基本思想：先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找。…直到查找成功，或者直到确定查找表中没有待查找的记录为止，即查找失败。
两者比较：
（1）顺序查找的查找效率很低；但是对于待查记录的存储结构没有任何要求，既适用于顺序存储，又适用于链式存储；当待查表中的记录个数较少时，采用顺序查找法较好。
（2）二分查找的平均查找长度较小，查找速度快；但它只能用于顺序存储，不能用于链式存储；且要求表中的记录是有序的。对于不常变动的有序表，采用折半查找法是较为理想的。
三、算法思想与算法描述
1、顺序查找，在顺序表R[0…n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示：
int SeqSearch(SeqList R[],int n,KeyType k) { int i=0; while(i<n&&R[i].key!=k) { printf("%d",R[i].key); i++; } if(i>=n) return -1; else { printf("%d",R[i].key); return i; } } 2、二分查找，在有序表R[0…n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下： int BinSearch(SeqList R[],int n,KeyType k) { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\n ",++count,low,high,mid,R[mid].key); if(R[mid].key==k) return mid; if(R[mid].key>k) high=mid-1; else low=mid+1; } return -1; }
四、实验任务
认真阅读与理解实验内容的具体要求，参考教材相关章节，编写实验程序并上机调试与测试，完成实验报告的撰写。
1.已知含有10个整数的查找表如下：（9，13，15，7，45，32，56，89，60，36），从键盘上输入一个整数，用顺序查找的方法在查找表中查找该整数。若存在，输出该元素的下标值，否则，给出相应的信息。
2.对有序数据表(5，7，9，12，15，18，20，22，25，30，100)，编写程序按折半查找方法查找12和28。
顺序查找：
#include <stdio.h> #include <stdlib.h> int SeqSearch(int R[],int n,int k) { int i=0; while(i<n && R[i]!=k) { printf("%d",R[i]); i++; } if(i>=n) return -1; else { printf("%d",R[i]); return i; } } int main() { int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int k, loc; printf("Please input your number: \n"); scanf("%d", &k); loc=SeqSearch(a, 10, k); printf("\n"); printf("The number's location is %d\n ", loc); return 0; }
二分查找：
#include <stdio.h> #include <stdlib.h> int BinSearch(int R[], int n, int k) { int low=0,high=n-1,mid,count=0; while(low<=high) { mid=(low+high)/2; printf("第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\n ",++count,low,high,mid,R[mid]); if(R[mid]==k) return mid; if(R[mid]>k) high=mid-1; else low=mid+1; } return -1; } int main() { int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int k, loc; printf("Please input your number: \n"); scanf("%d", &k); loc=BinSearch(a, 10, k); if(loc == -1) printf("not find!"); return 0; }
