【二分查找】学习总结
二分查找： （1） 一般的二分查找： 例如：找球号问题： 在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，现在说一个随机整数k(0<=k<=100000100)，判断编号为k的球是否在这堆球中（存在为"YES",否则为"NO"），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。 这就是普通的二分查找，把所有的球号存入ans[ ]数组了，从小到大排序，然后二分查找，假设共n个球吧（数组中0----n-1） 首先边界 fir=0，end=n-1， （1）一旦fir<end不成立，即break，说明不存在；否则使mid=（fir+end）/2； （2）然后比较 ans[mid] 与 要查找是否存在的球号k，若相等 即输出 YES； （3）如果 ans [ mid ] > k, 则 fir 不变，end=mid-1；（ans[]是从小到大排序的，ans[mid]的球号大于k，那么mid后面的球号必定也大于k，故缩小近一半区间），转至（1）步； （4）如果 ans [ mid ] < k, 则end 不变，fir=mid-1； （ans[]是从小到大排序的，ans[mid]的球号小雨k，那么mid前面的球号必定也小于k，~~~~转至（1）步； 练习题目：http://acm.nyist.net/JudgeOnline/problem.php?pid=86； 参考代码：http://blog.csdn.net/piaoyi0208/article/details/7270472；（2） 二分查找求下界： 看完一般的二分查找后，我们提一个问题，如果很多球号都是k，按照第一种写法（加上-找到球号时，返回该下标），会返回那个下标呢？第一个，最后一个？不难看出，都不是，怎样写能使 返回下标为 ans数组第一次出现k时的呢？若不存在k，在返回下标出插入k，后面的依次向后移一位，顺序不变！
//二分法求上界#include<cstdio>#include<cstring>#include<iostream>using namespace std;int main(){int ans[20]={0,1,2,3,3,3,3,3,4,5,7};//假设已经排好序了,查找球号 3int fir=0,end=10,mid;while(fir<end){mid=(fir+end)/2;if(ans[mid]<=3)fir=mid+1;else end=mid;}cout<<fir<<endl;/*输出结果是 8 */} 最近做比赛时，遇到了用二分查找边界的问题，代码写的很郁闷，以前写过二分查找判断一个数在是否存在一组数据里，遇到查找边界问题，郁闷了~~~好好学习下，总结一下.......