您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

029第六章 数组07 有序數組二分法求輸入值于數組中的索引

发布时间：2021-04-30 11:38:52编辑：雪饮阅读（）

 例7.10 假设在数组a中的数据是按由小到大顺序排列的：

 -12 0 6 16 23 56 80 100 110 115，从键盘上输入一个数，判定该数是否在数组中，若在，输出所在序号。
這個題目看起來就很容易，就算不用二分法，用傳統的挨個遍歷也是可以完成的。不過這裏主要是爲了介紹二分法，所以就用二分法來實現了。
這個二分法不記得是當時什麽時候的課程了，好像是高中的，也好像是大學的。且不管這些了。
先來看看它是如何定義的：
对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

那麽接下來看看如何通過c語言來實現它：
#define M 10
#include<stdio.h>
void main()
{
       static int a[M]={-12,0,6,16,23,56,80,100,110,115};
      int n, low, mid, high, found;
       low=0;
       //由于隊列是從小向大排序的，所以隊列的高數位位置是隊列長度-1
       high=M-1;   
       found=0;
       printf("Input a number to be searched:");
      scanf("%d", &n);
       while(low<=high){
              mid=(low+high)/2;
              /*每次輸入數和中間數對比，找到了，則结束循环*/       
              if (n==a[mid])
              {
                     found = 1;    
                     break;
              }
              //沒有找到，則底位數遞增(輸入數大于中間數，中間數的下一個數作爲低位數)，進行下一輪的中間數比較          
              else if (n > a[mid]){
                     low=mid+1;
              }
              //如果輸入數小于等于中間數，則高位數遞減，進行下一輪的中間數比較（即和輸入數相同的數有可能在左側，每次猜測的範圍為原範圍的一半）
              else {
                     high=mid-1;
              }     
       }
       //儅找到與輸入值相同的數，則因爲每次與中位數比較時候比較的是索引，所以此時就可以直接輸出目標數在數組中的索引位置了
       if (found==1) {
              printf("The index of %d is %d",n,mid);
       }
       //沒有找到，則就輸出原來的輸入數字
       else {
              printf("There is not %d",n);
       }
}