算法专题(一)  二分法

考虑一个问题:
从1～100内选一个数，然后让别人去猜，你只会告诉他他才的数字大了或者小了，怎么去快速猜到你选的数呢？
解决上面的问题就会用到二分法:
一直去猜中间的数，如果大了，就抛弃中间的数和右边的所有数字;如果小了，就抛弃中间的数和左边的所有数字。如此重复下去，直到猜中数字。

来看看代码吧:

查找数列里第一个大于等于val的值，返回下标 先判断中间的数，如果小于我们要找的key，那么就把左边的数列，包括中间的都抛弃掉first=middle+1,否则就保留中间的数，抛弃掉右边的数列。

int my_lower_bound(int *arr, int size,int key){
int left=0,right=size;
int mid;
while(left<right){
mid=(left+right)>>1;
if(arr[mid]<key)
      left=mid+1;
else
      right=mid;
}
return left;
}

查找数列里第一个大于val的值，返回下标 可以看到，这个和lower_bound相比较而言只是改变了if else的顺序。先上代码，看了你就会知道。

int my_upper_bound(int *arr, int size,int key){
int left=0,right=size;
int mid;
while(left<right){
mid=(left+right)>>1;
if(arr[mid]>key)
      right=mid;
else
      left=mid+1;
}
return left;
}

可以看到:
1.如果查找第一个大于等于val的值，会抛弃掉所有小于val的值。
2.如果查找第一个大于val的值，会抛弃掉所有小于等于val的值。