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

在有序表中查找元素常常使用二分查找，有時也譯為“折半查找”，二分查找的基本思路為逐漸縮小范圍，它遵循分治三步法，把原序列劃分成元素個數盡量接近的兩個子序列，然后遞歸查找。二分查找只適用于有序數列，時間復雜度為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循環常常寫在程序中。二分查找常常用在一些抽象的場合，沒有數組a，也沒有要查找的數，但是二分的思想仍然適用。

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

下面的程序，當v存在時返回它出現的第一個位置。如果不存在，返回這樣一個下標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的各種關系所帶來的影響如下：

1，a[m]=v：至少已經找到一個，但左面可能還有，因此區間變為[x,m]；

2，a[m]>v：說明v在a[m]的左邊，區間變為(x,m)；

3，a[m]<v：說明v在a[m]的右邊，區間變為(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;

}