顺序查找、折半查找

1顺序查找与折半查找的比较顺序查找简单的从头到尾的查找，对数据没有要求，而折半查找要求查找的数据是按顺序排列的，然后找中间数，若中间数大，则把中间数当成最后一个数找他们的中间数。反之，则把中间数当成第一个数。找他们的中间数。这样，一直找下去，直到找到或者中间数和第一个数或者最后一个数相等。它较顺序查找，效率较高。依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：查找表1：{8，15，19，26，33，41，47，52，64，90}，查找key=41查找表2：{12，76，29，15，62，35，33，89，48，20}，查找key=35查找key=41的算法：比较次数：查找key=35的算法：比较次数：查找key=41的算法：折半查找法比较次数：3次查找key=35的算法：顺序查找法比较次数：6次顺序查找算法实现代码：intSequenceSearch(inta[],intn,intkey){inti=0,cnt=0;for(i=0;in;i++){cnt++;if(a[i]==key){printf(\nSequencialSearchcomparetimes:%d,cnt);returnkey;}}return-1;}l折半查找算法实现代码：intBinarySearch(inta[],intn,intkey){intlow=0,high=n-1,mid=0;intcnt=0;while(low=high){cnt++;mid=(low+high)/2;printf(\ncompare%dwith%d,a[mid],key);if(a[mid]==key){printf(\nSequencialSearchcomparetimes:%d,cnt);returnkey;}if(a[mid]key){high=mid-1;}else{low=mid+1;}}return-1;}2/*折半查找法例题1*/#includestdio.hvoidmain(){inta[10]={8,18,27,42,47,50,56,68,95,120};intb=8;//要查找的数intmin=0;intmax=9;intmid=(min+max)/2;while(b!=a[mid]){if(ba[mid]){min=mid;mid=(min+max)/2;}elseif(ba[mid]){max=mid;mid=(min+max)/2;}if(mid==min)break;}if(b==a[mid]){printf(a[%d]=%d\n,mid,a[mid]);}elseif(b==a[max]){printf(a[%d]=%d\n,max,a[max]);}elseprintf(没有此数\n);}/*折半查找法例题2*/#includestdio.hintmain(){intkey=0;printf(请输入要查找的数：);scanf(%d,&key);intdata[10]={1,3,5,7,8,9,13,18,22,28};intret=BinarySearch(key,data);if(ret=0)printf(\n%d是数组中的第%d个数\n,key,ret+1);elseprintf(\n%d在数组中未找到！\n,key);system(pause);return0;}intBinarySearch(intkey,intdata[]){intlow=0,high=9,middle;while(low=middle){/*查找结束条件*/intmiddle=（low+high）/2;/*获取数组中间位置*/3if(key==data[middle])/*如查当前数据元素的值等于key*/returnmiddle;/*返回所在位置*/if(keydata[middle])/*如果若k小于当前数据元素的值*/high=(low+middle)/2;/*在数组的前半部继续查找*/elselow=(middle+high)/2/*在数组的后半部继续查找*/}return-1;/*返回查找不成功标记*/}/*简单排序法*/#includestdio.h#defineN6voidswap(int*a,int*b){intt;t=*a;*a=*b;*b=t;}voidmain(){inta[6]={15,14,22,30,37,11};intmin;for(inti=0;iN-1;i++){min=i;for(intj=i+1;jN;j++){if(a[i]a[j])min=j;}swap(a+i,a+min);}for(i=0;iN;i++)printf(%d,a[i]);}2013年高考题36.折半查找也称为二分查找，适用于有序数组，其查找的基本过程是：先确定待查记录所在的范围，然后逐步缩小范围，直到找到，或找不到该记录为止。假定数组按照升序排列，对于给定值K，从数组中间位置开始比较，如果当前数据元素的值等于k，则查找成功。否则，若k小于当前数据元素的值，则在数组的前半部继续查找；反之，则在数组的后半部继续查找，依次重复进行，直至获得查找成功或不成功的结果。请补充完成下列程序中的相应部分：#includestdio.h4intmain(){intkey=0;printf(请输入要查找的数：);scanf(%d,&key);intdata[10]={1,3,5,7,8,9,13,18,22,28};intret=BinarySearch(key,data);if(ret=0)printf(\n%d是数组中的第%d个数\n,key,ret+1);elseprintf(\n%d在数组中未找到！\n,key);system(pause);return0;}intBinarySearch(intkey,intdata[]){intlow=0,high=9,middle;while(①){/*查找结束条件*/intmiddle=②;/*获取数组中间位置*/if(③)/*如查当前数据元素的值等于k*/returnmiddle;/*返回所在位置*/if(keydata[middle])/*如果若k小于当前数据元素的值*/④;/*在数组的前半部继续查找*/else⑤/*在数组的后半部继续查找*/}return-1;/*返回查找不成功标记*/}