折半查找法

查找是在程序设计中最常用到的算法之一，假定要从n个整数中查找x的值是否存在，最原始的办法是从头到尾逐个查找，这种查找的方法称为顺序查找。这种方法效率低。假如要从1000个数据中要查找某一个所需的数据，而该数据恰恰是最后一个，则需要取数据和比较数据1000次。对n个数据的平均取数和比较的次数为n/2次。 折半查找的速度有所改进，但是只适用于巳排好序的数列。其基本思路是：先检索中间的一个数据，看它是否为所需的数据，如果不是，则p判断要找的数据是在中间数的哪一边，下次就在这个范围内查找。

折半查找的算法如下：
首先需要设三个指示器top，mid,foot 分别指向数列的开头，中间和末尾，假定有15个元素，开始时令top=0, foot=14,mid=(top+foot)/2=7。接着进行以下判断：
(1) 如果x=[mid]则设查到标志为“真”，打印有关信息。
(2) 否则如果x<a[mid] 则下一步查找范围应该在a[top]到a[mid-1]之间，改变foot使之等于mid-1，即top=mid-1。(3) 如果x>a[mid]则下一步查找范围应该在a[mid+1]到a[foot]之间，改变top使之等于mid+1，即top=mid+1。
程序如下:
#include <stdio.h>
#define N 21
void main(void)
{
int a[N];
int i,n,num;
int top,bottom,mid;
int flag=1; //如果在表列中找到数字，则值为1，否则为0
int loc=-1;//要查找的数在表列中的位置，如果loca=-1表示表列中没有这个数;如果有这个数,则它的值为所在的位置

printf("你想在多少个数中进行折半查找，请输入（1--20）：");
scanf("%d",&n);

while(n<1 || n>20)
{
   printf("你输入的数不正确，请重新输入。\n");
   printf("你想在多少个数中进行折半查找，请输入（1--20）：");
   scanf("%d",&n);
}

printf("请你输入一个整数 a[1]:");
scanf("%d",&a[1]);

i=2;
while(i<=n)   //输入从小到大的表列
{
   printf("请你输入一个整数 a[%d]:",i);
   scanf("%d",&a[i]);
   if(a[i] > a[i-1])
    i++;
   else
    printf("你输入的数不满足要求，请重新输入。\n");
}

//输出表列
printf("\n输出表列\n");
for(i=1; i<=n; i++)
{
   printf("%6d",a[i]);
}
printf("\n");

printf("请你输入要查找的数：");
scanf("%d",&num);

flag=1; //假设输入的数在表列中

top=1;
bottom=n;
mid=(top+bottom)/2;

while(flag)  
{
   printf("top=%d, bottom=%d, mid=%d, a[%d]=%d\n",top,bottom,mid,mid,a[mid]);
   if( (num>a[top]) || (num<a[bottom]) ) //输入的数 num>a[top] 或者 num<a[bottom]，肯定num不在这个表列中
   {
    loc=-1;
    flag=0;
   }
   else if(a[mid]==num) //如果num 等于找到的数
   {
    loc=mid;
    printf("找到数 %6d 的位置%2d\n",num,loc);
    break;
   }
   else if(a[mid]>num) //若 a[mid]>num，则num 一定在 a[top]和a[mid-1]范围之内
   {
    bottom=mid-1;
    mid=(top+bottom)/2;
   }
   else if(a[mid]<num) //若 a[mid]<num，则num 一定在 a[mid+1]和a[bottom]范围之内
   {
   top=mid+1;
    mid=(top+bottom)/2;
   }
}

if(loc==-1)
{
   printf("%d 这个数在表列中没有找到。\n",num);
}

}

另一个程序：