從1000000個整數(shù)中找到1234，最容易想到的方法是把他們放在a數(shù)組中再一個個去檢查這些數(shù)是否為1234,。這樣的方式對于尋找一個數(shù)很可行，但是如果要找100個數(shù)，就需要把a數(shù)組遍歷100次。而如果先將a數(shù)組排序，就可以查找得更快。

在有序表中查找元素常常使用二分查找，有時也譯為“折半查找”，二分查找的基本思路為逐漸縮小范圍，它遵循分治三步法，把原序列劃分成元素個數(shù)盡量接近的兩個子序列，然后遞歸查找。二分查找只適用于有序數(shù)列，時間復雜度為O(logn)。

代碼如下：

int bsearch(int*a,int x,int y,int v)

{

      int m;

      while(x<y)

      {

             m=x+(y-x)/2;

             if(a[m]==v)       return m;

             else if(a[m]>v)      y=m;

             else  x=m+1;

      }

      return -1;

}

上述while循環(huán)常常寫在程序中。二分查找常常用在一些抽象的場合，沒有數(shù)組a，也沒有要查找的數(shù)，但是二分的思想仍然適用。

如果數(shù)組中有多個數(shù)都為v，上面的函數(shù)返回的是哪一個的下標呢？顯然會是中間那一個。有時，這樣的結(jié)果并不是很理想，能不能求出值等于v的完整區(qū)間呢？

下面的程序，當v存在時返回它出現(xiàn)的第一個位置。如果不存在，返回這樣一個下標i：在此處插入v(原來的元素a[i],a[i+1]......全部往后移動一個位置)后序列仍然有序。

int lower_bound(int *a,int x,int y,int v)

{

       int m;

       while(x<y)

       {

               m=x+(y-x)/2;

               if(a[m]]>=v)     y=m;

               else x=m+1;

        }

        return x;

}

a[m]和v的各種關(guān)系所帶來的影響如下：

1，a[m]=v：至少已經(jīng)找到一個，但左面可能還有，因此區(qū)間變?yōu)閇x,m]；

2，a[m]>v：說明v在a[m]的左邊，區(qū)間變?yōu)?x,m)；

3，a[m]<v：說明v在a[m]的右邊，區(qū)間變?yōu)?m+1,y)；

int upper_bound(int *a,int x,int y,int v)

{

       int m;

       while(x<y)

       {

               m=x+(y-x)/2;

               if(a[m]]>v)     y=m;

               else x=m+1;

        }

        return y;

}