典型例题3第页共NUMPAGES2页广东海洋大学GuangdongOceanUniversityC语言程序设计技能训练试题（典型例题3））TrainingItem【题目】：有15个数按由小到大顺序存放在一个数组中，输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。如果该数不在数组中，则打印出“无此数”。【问题分析与算法设计】：折半查找法：假如有已按由小到大排好序的9个数，a[1]～a[9]，其值分别为：1、3、5、7、9、11、13、15、17。若输入一个数3，想查3是否在此数列中，先找出表列中居中的数，即a[5]，将要找的数3与a[5]比较，a[5]的值是9，发现a[5]>3，显然3应当在a[1]到a[5]范围内，而不会在a[6]到a[9]范围内。这样就可以缩小查找范围，甩掉a[6]到a[9]这一部分，即将查找范围缩小一半。再找a[1]到a[5]范围内的居中的数，即a[3]，将要找的数3与a[3]比较，a[3]的值是5，发现a[3]>3，显然3应当在a[1]到a[3]范围内。这样又将查找范围缩小一半。再将3与a[1]到a[3]范围内的居中的数a[2]比较，发现要找的数3等于a[2]，查找结束。一共比较了3次，如果表列中有n个数，是最多比较的次数为int(log=n)+1。【程序源代码、说明及注释】：#include<stdio.h>#defineNUM15voidmain(){inta[NUM],i,low=0,high=NUM-1,mid,n;printf("pleaseinput%dnumbersbeingsorted(frommintomax)to\arraya:\n",NUM);/*当一条语句要占多行时，必须在后面加上”\”*//*该数组必须是排好序了（这是二分法的要求），这里按从小到大排序。*/for(i=0;i<NUM;i++)scanf("%d",&a[i]);printf("Inputthenumberyouwanttofind:");scanf("%d",&n);while(low<high){mid=(low+high)/2;if(n>a[mid])low=mid+1;;/*中间数字比要查的数小，说明可能在中间段以后*/elseif(n<a[mid])/*中间数字比要查的数大，说明可能在中间段以前*/high=mid-1;else/*中间数字与要查的数相等，则输出要查找的数在原数组中的位置*/{printf("%disinthepositionofa[%d]",n,mid);break;}}if(low==high)/*没有找到*/printf("Datanotfound!");}