8.二分查找[单元素||多元素]难点剖析

8.二分查找

[置顶] 犯了一个错误

1.14日更新改正: 如果查询上界>int型的一半 那么mid=（zuo+you）/2 可能会溢出
故可以写成减法形式 ：mid= zuo+（you-zuo）/2

1. 二分查找算法

注意：二分上界超过int型数据范围的一半，那么当欲查询元素在序列较靠后的位置时，语句mid=（left+right）/2中的left+right就有可能超过int而导致溢出
此时一般使用mid=left+（right-left）/2这条等价语句作为代替以避免溢出。

源代码：
无重复元素时
此时查找区间段是 [0,n-1]; n为数组长度

/*
无重复元素时
此时查找区间段是 [0,n-1];   n为数组长度
*/
#include <bits/stdc++.h>
using namespace std;
int midso(int a[],int zuo,int you,int x)
{
	int mid;
	while(zuo<=you)
	{
		mid=(zuo+you)/2;   //去中间位置
		if(a[mid]==x) return mid;
		else if(x<a[mid]) you=mid-1;
		else zuo=mid+1;
	}	
} 
int main()
{
	int a[10]={0,1,2,3,4,5,6,7,8,9};
	cout<<midso(a,0,9,7);
	return 0;
}

---

2. 二分查找升级版 [ 查询的数组元素可以重复 ]

查询的数组元素可以重复 此时就需要算出区间
例如N [ ] = {1 2 3 4 5 6 6 6 7 8}; 被查找元素：6
区间：[ 5,8 ) 左闭右开形式
源代码：
有重复元素时
此时查找区间段是 [0,n]; n为数组长度

源代码：

/*
有重复元素
此时查找区间段是 [0,n];   n为数组长度 
*/
#include <bits/stdc++.h>
using namespace std;
int xiajie(int a[],int zuo,int you,int x)
{
	int mid;
	while(zuo<you)   // zuo==you意味着唯一元素  故不取= 
	{
		mid=(zuo+you)/2;
		if(x<=a[mid]) you=mid; 
		else zuo=mid+1;
	}	
	return zuo;
} 
int shangjie(int a[],int zuo,int you,int x)
{
	int mid;
	while(zuo<you)   // zuo==you意味着唯一元素  故不取= 
	{
		mid=(zuo+you)/2;
		if(x<a[mid]) you=mid; 
		else zuo=mid+1;
	}	
	return zuo;
} 
int main()
{
	int a[10]={0,1,2,3,6,6,6,7,8,9};
	cout<<"["<<xiajie(a,0,10,6)<<"，"<<shangjie(a,0,10,6)<<")";
	return 0;
}

---

其实上界 和 下界 的区别在于 x<=a[mid] 换成 x<a[mid] 理解即可 不用死记；