折半查找算法代码,C代码库,德仔网

代码语言

代码分类

【C】折半查找算法

作者:Dezai.CN / 发布于2013/1/8/ 746

//折半查找法
/*
 * 从表列中查一个数最简单的方法是从第1个数开始顺序查找，将要找的数与表列中的
   数一一比较，直到找到为止（如果表列中无此数，则应找到最后一个数，然后判定“找不到”）
   但这种“顺序查找法”效率较低。如果表列中有1000个数，且要找的数恰恰是第1000个数，
   则要进行1000次比较才得到结果。平均比较次数为500次。

  折半查找法是效率较高的一种方法，基本思路如下：
  假如有已按由小到大排好序的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[1]到a[5]范围内的居中的数，即a[3]
  将要找的数3与a[3]比较，a[3]的值为5,发现a[3]>3，显然3应当在a[1]到a[3]范围内
  再将查找范围缩小一半，与a[1]到a[3]范围内的居中的数a[2]比较，发现要找的数3等于a[2],查找结束
  一共比较了3次
   
*/
#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=n;
 bottom=1;
 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[bottom]和a[mid-1]范围之内
  {
   top=mid-1;
   mid=(top+bottom)/2;
  }
  else if(a[mid]<num) //若 a[mid]<num，则num 一定在 a[mid+1]和a[top]范围之内
  {
   bottom=mid+1;
   mid=(top+bottom)/2;
  }
 }
 
 if(loc==-1)
 {
  printf("%d 这个数在表列中没有找到。/n",num);
 }

}

评论列表

本站所提供的代码，版权归原作者所有，若有侵犯作者版权，请与我们联系，我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。

试试其它关键字

　折半查找　

同语言下

可能有用的

Dezai.CN贡献的其它代码(4037)