二分法

STL中的二分法

数组是{1,2,4,4,5,6}

在STL中lower_bound()是返回第一个非递减序列中的第一个大于等于val的位置，写法是lower_bound(v.begin(),v.end(),target);这样就会指的是第三个元素

在STL中upper_bound()是返回第一个大于val的位置，所有对于这个函数返回的是值为5的元素。

用STL写二分查找

输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 1,2,…,a1​,a2​,…,an​，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

题解：这里就是用函数lower_bound()来返回第一个大于等于，然后想返回序列号就用distance()，然后数组第一个的位置是1，所有需要在原有基础上加1，然后对于判断就是it不能等于end，把并且it的值要和对应的target相同，而it的值就是星号it。

代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
typedef long long ll;
constexpr int N = 1e6+10;
void solve(){
	int n;
	int m;
	cin>>n>>m;
	vector<int> a;
	for(int i = 0;i<n;i++){
		int x;
		cin>>x;
		a.push_back(x);
	}
	while(m--){
		int target;
		cin>>target;
		auto it =lower_bound(a.begin(),a.end(),target);
		if(it!=a.end()&&*it==target){
			cout<<distance(a.begin(),it)+1<<' ';
		}
		else cout<<"-1 ";
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();	
}

实数范围的二分（带小数）

对于实数二分来说，是有许多解决方法，比如说求单调函数的零点或者极值。另外就是满足某种条件的最优解；或者是解决一些复杂度较高的问题。

用二分法求解函数零点的例子，首先要定义一个函数是对应的表达式。然后小数二分的一个技巧是right-left要大于某个exp值，才会继续往下循环，然后就是最常规的二分操作。

举个例子，对于f(x) = x^2-2，精度为1e-6，要通过二分法求零点的话。

#include<iostream>
#include<cmath>
double f(double x){
	return x*x-2;
}

int main(){
	double left = 0,right = 2,eps = 1e-6;
	while(right-left>eps){
		double mid = left+(right-left)/2;
		if(f(mid)>0){
			right = mid;
		}
		else{
			left = mid;
		}
	}
	cout<<"零点是:"<<left<<"\n";
	return 0;
}

P1024 一元三次方程求解

题目有形如：ax^3+bx^2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数（a,b,c,d 均为实数），并约定该方程存在三个不同实根（根的范围在 −100至 100 之间），且根与根之差的绝对值 ≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 2 位。

提示：记方程 f(x)=0，若存在 2 个数 x1​ 和 x2​，且 x1​<x2​，f(x1​)×f(x2​)<0，则在 (x1​,x2​) 之间一定有一个根。

输入和输出案例

1 -5 -4 20

-2.00 2.00 5.00

题目解析

这就是典型的函数零点求解。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
double a,b,c,d;//定义全局变量，在函数和主程序里面都有用 
double f(double x)
{
    return (a*x*x*x+b*x*x+c*x+d);//万能函数，求出在未知数为x时的方程解 
}
int main()
{
    double x1,x2,xx;
    cin>>a>>b>>c>>d;//输入 
    for(int x=-100;x<=100;x+=1)//枚举每一个可能的根 
    {
        x1=x;x2=x+1;//确定根可能所在的区间 
        if(f(x1)==0)printf("%.2f ",x1);
        else if(f(x1)*f(x2)<0)
             {
                 while(x2-x1>=0.001)//二分法确定根的值 
                 {
                      xx=(x1+x2)/2;
                      if((f(x1)*f(xx))<=0)x2=xx;
                      else x1=xx;
                 }
                 printf("%.2f ",x1);//输出根 
             }
    } 
}

对于二分法区间的操作

二分法总结 | 万字长文带你看透二分查找 - 知乎 (zhihu.com)