c++二分查找

二分查找        

二分查找分为靠左和靠右。

是一种节省时间的算法。

由于每次运算减少一半的计算量，所以算法时间为O(logn)。

下图为每一个去枚举和二分查找的次数对比

整数二分

        靠左函数        

        进行查找时，尽可能的找到符合条件的靠左值。此时，需要注意如果当前切割点mid符合条件，那应该保留答案，且删除右区间，靠左继续二分，直到不可二分。

int ask(int x){
	int l=1,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]>=x)	r=mid;
		else l=mid+1;
	}
	if(a[l]!=x)	return -1;
	return l;
}

        靠右函数

        进行查询时，尽可能的找到符合条件的靠右值/最大值。此时需注意如果当前切割点mid符合条件，那应保留答案，且删除左区间，靠右继续二分，直到不可再分。

int ask(int x){
	int l=1,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(x>=a[mid])	l=mid;
		else r=mid-1;
	}
	if(a[l]!=x)	return -1;
	return l;
}

        总体代码展示

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1145141];
int ask(int x){
	int l=1,r=n;
	while(l<r){
		int mid=l+r+1>>1;
		if(x>=a[mid])	l=mid;
		else r=mid-1;
	}
	if(a[l]!=x)	return -1;
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int x;cin>>x;
	cout<<ask(x);
	return 0;	
}

实数二分

对于实数的二分，与整数二分主要的差异体现在以下两个方面：
1.实数不会出现因整数取整而导致的mid偏向问题。即double mid=(l+r)/2，不用考虑会因为mid错误导致死循环。
2.实数中，两个相邻的数字间隔不一定是1，所以不能用加减1来进行寻找。最后找到的数字也可能是相似值，所以只要满足精度即可。
一般来说如果题目要求保留k位小数，此时l,r是不一样的。我们会把精度设置到小数点后k+2位。（k+1位会对第k位的进位产生很大影响，k+2位相对好一点。），此时输出l或r基本相同

#include<bits/stdc++.h>
using namespace std;
double n,eps=1e-8;
bool check(double x){
    return x*x*x>=n;
}
int main(){
    cin>>n;
    double l=1,r=n;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid;
    }
    printf("%6lf",l);
    return 0;
}
//求n的三次方根

二分查找相关函数

若存在序列a={0,1,3,3,3,5,8}

1.binary_search(a+1,a+n+1,x)

查找单调序列中，在指定区域内[1,n]是否存在目标值x。存在返回true,不存在返回false。

int k=binary_search(a+1,a+7,3)；//k=1

2.lower_bound(a+1,a+n+1,x)

查找不降序列中，在指定区域内[1,n]大于等于目标值x的第一个元素所在地址。(靠左查找)

int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+2，因此pos=2。

3.upper_bound(a+1,a+n+1,x)

查找不降序列中，在指定区域内[1,n]大于目标值x的第一个元素所在地址。(靠右查找)

int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+5，因此pos=5。

谢谢各位