二分查找

从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;

}