text2.cpp

数据结构的实验,是查找那一章节的,用二分法查找!

#include <stdio.h>
#define N 100
void main(void)
{
 int a[N];
 int i,n,num;
 int high,low,mid;
 int flag=1; //如果在表列中找到数字，则值为1，否则为0
 int loc=-1;//要查找的数在表列中的位置，如果loca=-1表示表列中没有这个数;如果有这个数,则它的值为所在的位置
 printf("你想在多少个数中进行折半查找，请输入（1--100）：");
 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; //假设输入的数在表列中
 high=n;
 low=1;
 mid=(high+low)/2;
 while(flag)  
 {
  printf("High=%d, Low=%d, Mid=%d, a[%d]=%d\n",high,low,mid,mid,a[mid]);
  if( (num>a[high]) || (num<a[low]) )  //输入的数 num>a[high] 或者 num<a[low]，肯定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[bottom]和a[mid-1]范围之内
  {
   high=mid-1;
   mid=(high+low)/2;
  }
  else if(a[mid]<num) //若 a[mid]<num，则num 一定在 a[mid+1]和a[top]范围之内
  {
   low=mid+1;
   mid=(high+low)/2;
  }
 }
 if(loc==-1)
 {
  printf("%d 这个数在表列中没有找到。\n",num);
 }
printf("输入任意键后回车结束！");
 scanf("%d",&n);
}