二分查找 使用指南
二分查找 使用指南
二分查找
一、没有相同元素查找
请在一个有序递增数组中（不存在相同元素），采用二分查找，找出值x的位置，如果x在数组中不存在，请输出-1！
输入格式
第一行，一个整数n，代表数组元素个数（n <= 600000）
第二行，n个数，代表数组的n个递增元素（1<=数组元素值<=2000000）
第三行，一个整数x，代表要查找的数（0<=x<=2000000）
输出格式
按题意输出位置或者-1。
输入/输出例子1
输入：
10
1 3 5 7 9 11 13 15 17 19
3
输出：
2
【分析】：当我们要从一个序列中查找一个元素的时候，最快想到的方法就是顺序查找法（即：从前到后依次查找）。但这种方法过于无脑，就是暴力的把每个元素都排查一遍。元素个数少的时候还行，一旦元素个数多起来，效率非常低下。
二分查找法也称折半查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log2n)完成查找任务。
它的基本思想是，先把n个元素从小到大排序，然后取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x＜a[n/2]，则我们只要在数组a的左半部分继续搜索x。如果x＞a[n/2]，则我们只要在数组a的右半部分继续搜索x，直到查找成功或查找完毕为止。
以下是二分查找的查找过程图示：
二分查找的算法框架一如下：
left=1;right=n;
while(left<=right)
{
mid=(left+right) / 2;
if (x==a[mid]){ 查找成功，输出mid的值并结束;}
if (x>a[mid]) left=mid+1;//往数组的右边找
if (x<a[mid]) right=mid-1;//往数组的左边找
}
输出“查找不成功”
在查找过程中我们每次把查找的范围缩小了一半，在最坏情况下查找log2n次就可以得到结果。
注意：
1．二分查找是在数据有序的情况下才能完成，即进行二分查找前数据必须先排序。上述框架是以数据已从小到大排序为前提条件的。
2．这里可能解的范围为[left,rigth],当x＞a[mid]时，x如果存在的话应该是在数组的[mid+1,right]中，此时的left改为mid+1，而不是mid；同理，当x＜a[mid]时，x如果存在的话应该在数组的[left,mid-1]里，此时的right应该改为mid-1，而不是mid。
二分查找的算法框架二如下：
left=0;right=n+1;
while(left+1<right)
{
mid=(left+right) / 2;
if (x==a[mid]){ 查找成功，输出mid的值并结束;}
if (x>a[mid]) left=mid;//往数组的右边找
if (x<a[mid]) right=mid;//往数组的左边找
}
输出“查找不成功”
二、有相同元素的查找
1、求左侧边界：
这样就引申出一个问题：如何二分查找求左侧边界。当查找的数字v存在时，得到它出现的第一个位置，假如不存在，就得到比它大的第一个数的位置。
这样只要把二分查找修改一下：
为了查找方便，我们在数组a[0]处插入一个最小的数-1，在a[n+1]处插入一个无穷大数，left指向0，right指向n+1，这样解空间为（left,right]。
1、 情况a[mid]>=v时：right=mid(至少已经找到一个，或者mid可能已经是比v大的数中最小的一个，或者左边可能还有比v大的，因此区间变成（left,mid]。）
2、 情况a[mid]<v时；left=mid，也就是解只可能在右边。
例如：
-1 2 3 5 6 7 7 8 10000000 中查找v=7
第一轮：left=0,right=9,解空间为(0,9]那么mid=(0+9)/2=4,因为a[4]=6<7,那么left=mid=4,解空间应该是(4,9]。
第二轮left=4,right=9, mid=(4+9)/2=6 ,因为a[6]=7==7,那么right=6,也就是解空间为（4,6]。
第三轮 left=4,right=6, mid=(4+6)/2=5 ,因为a[5]=7==7,那么right=5,也就是解空间为（4,5]。
因为解空间只有一个解，所以解为下标5，所以left+1==right为程序结束条件。
【求下界核心程序如下】：
a[n+1]=1000000000;
a[0]=-1;
int findleft(int left,int right,int value)//调用时left=0,right=n+1
{
while(left+1<right) //如果解区间不止一个，那么继续二分
{
int mid=(left+right)/2; //取中间值
if(a[mid]>=value)//如果找到一个等于或者大于value的数，解空间为(left,mid]
right=mid;
else
left=mid; //如果找到一个小于value的数，解空间为(mid,right]
}
return right;
}
2、求右侧边界
如何二分查找求右侧边界。当查找的数字v存在时，得到它出现的最后一个位置，假如不存在，得到比它大的第一个数的位置。
方法如下：
为了查找方便，我们在数组a[0]处插入一个最小的数-1，在a[n+1]处插入一个无穷大数，left指向0，right指向n+1，这样解空间为[left,right)。
1、 情况a[mid]>v时：right=mid，也就是解只可能在左边。
2、 情况a[mid]<=v时；left=mid(至少已经找到一个，或者mid可能已经是比v大的数中最小的一个，或者右边可能还有比v大的，因此区间变成[right,mid)。
【求上界核心程序如下】：
a[n+1]=1000000000;
a[0]=-1;
int findright(int left,int right,int value)//调用时left=0,right=n+1
{
while(left+1<right) //如果解区间不止一个，那么继续二分
{
int mid=(left+right)/2;
if(a[mid]<=value)//找到一个小于或者等于value的数，解空间为(mid,right]
left=mid;
else
right=mid; //如果找到一个大于value的数，解空间为(left,mid]
}
return left;
}
小结：
（1）求左侧边界，返回右端点；（L,R]。
（2）求右侧边界，返回左端点。[L,R)。
拓展：另外一种二分查找形式找左侧和右侧：
根据c++的整除是求下界，那么两个相邻的数求平均数等于较小的数，也就是当求区间解时，当左区间不能满足要求时，可以让left=mid+1，跳出条件变为L<R，也就是解空间为(L,R]。
找左侧程序如下：
int L=0,R=n+1,mid;
while(L<R)
{
mid=(L+R)/2;
if(a[mid]<x)
L=mid+1;
else
R=mid;
}
if(a[R]==x) printf("%d ",R);
else printf("-1 ");
找右侧程序如下：
int L=1,R=n+1,mid;
while(L<R)
{
mid=(L+R)/2;
if(a[mid]<= x)
L=mid+1;
else
R=mid;
}
if(a[L]==x) printf("%d ",L);
else printf("-1 ");