C语言中的二分查找（折半查找）

 

为了提高查找效率，在一个数组中查找某个数据是否存在时，可以先将数组数据排序,将排序后的数列的中点设置为比较的对象，如果要找的元素的值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。即根据比较的结果排除掉数组一半的元素，再在余下的一半数组元素中取中间的一个元素进行比较，并根据比较的结果再次排除一半的数组元素，以此类推，直至最终找到为止。这就是二分查找（Binary Search），由于二分查找法每次都根据比较结果排除一半的数据，因此也称为“折半查找法”。二分查找的先决条件是：查找表中的数据元素必须有序。在二分法中，只能对递增的数组进行查找。

 

算法步骤：

1、首先是确定整个查找区间的中间位置，mid = ( left + right )/2；

2、用待查数据的值与中间位置的数据值进行比较：若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。（这步是循环的过程）

3、用二分查找法对确定后的区域再次进行范围缩小的查找，直到查找到结果为止。

 

下面举个例子:用随机函数rand产生一个100内的10个元素的数组，用键盘输入一个数字，用二分法查找。若找到打印出位置，若没有，则输入无次数。

 

#include <stdio.h>

#include <stdlib.h>

void main()

{

     int a[10],i,j,temp,min,t,site;

     for(i=0;i<10;i++)

         {

         a[i]=rand()%101;//用随机函数产生一个--100的包含个元素的无序数组

         /*printf("%d ",a[i]);*/

         }

     printf("随机产生的数组为：");

     for(i=0;i<10;i++)

         printf("%d ",a[i]);

     //以上为随机产生数组过程

 

     printf("\n");//换行

 

     for(i=0;i<10;i++)

         {    min=a[i];

              t=i;

              for(j=i+1;j<10;j++)

              {

                   if(a[j]<min)

                   {

                       min=a[j];

                       t=j;

                   }

              }

              temp=a[i];

              a[i]=a[t];

              a[t]=temp;

              /*printf("%d ",a[i]);*/ //在这里输出排序后的数组也可以。

         }

     printf("排序后的数组为：");

     for(i=0;i<10;i++)

         printf("%d ",a[i]);

     //以上为排序过程

 

     printf("\n"); //换行

 

     printf("请输入要查找的数字：");

     int find;

     scanf("%d",&find);

     int low = 0;//定义数组低位下标并赋初值

     int high = 9;//定义数组高位下标并赋初值

     int mid;//定义数组中间下标

     site = -1;

     while(low<=high)

     {

         mid=(low+high)/2;

         if(find==a[mid])

              {

                   site=mid;//将找到的下标值赋给site,site主要用来记录所找数的位置

                   break;

              }

         else

              {

                   if(find<a[mid])

                       high=mid-1;//将高位往左移，确定查找的终点。用high=mid也可以，只是多计算一次。

                   else

                       low=mid+1;//将低位往右移，确定查找的起点。用low=mid也可以，只是多计算一次。

 

              }

 

     }

     if(site != -1)

         printf("找到了你所需要查找的数字%d，是第%d个数\n",find,site+1);

     else

         printf("没有找到你输入的数字。");

     //以上为二分法查找过程

}