2. 二分查找
整数二分
二分的本质不是单调性，有单调性一定可以二分，可以二分不一定有单调性 二分的本质是边界，假设给定一个区间，如果能够根据某个条件，将区间划分为左右两部分，使得左半边满足这个条件，右半边不满足这个条件（或者反之）。就可以用二分来查找左右两部分的边界点。
主要思想：假设这组数据关键字已有序
1.寻找红色区间的右边界点 模板一
当l<r时不断循环
先取中间值
mid=(l+r)/2先判断mid是否满足条件（即某种性质），
check(mid)
- 若满足，
check(mid)为true，区间更新为[l,mid]，即r=mid；- 若不满足，
check(mid)为false，更新区间为[mid+1,r]，即l=mid+1。（注意这里mid+1，是因为mid本身已不满足条件，只能右移一个位置去区间找答案。）最后
l=r，循环结束，输出分界点位置l(或r)
代码模板：
int binarysearch_1(int l,int r){
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
return l;//return r;也可
}2.寻找绿色区间的左边界点 模板二
当l<r时不断循环
先取中间值
mid=(l+r+1)/2
- 注意，当采用
l = mid和r = mid - 1这种更新方式时，计算mid时，要加上1（向上取整），即mid = l + r + 1 / 2。否则，在l = r - 1时，计算mid时若不加1，则mid = l + r / 2 = l，这样更新l = mid，就是l = l，会导致死循环。所以要向上取整，采用mid = l + r + 1 / 2。先判断mid是否满足条件（即某种性质），
check(mid)
- 若满足，
check(mid)为true，区间更新为[mid,r]，即l=mid；- 若不满足，
check(mid)为false，更新区间为[l,mid-1]，即r=mid-1。（注意这里mid-1，是因为mid本身已不满足条件，只能左移一个位置去区间找答案。）最后
l=r，循环结束，输出分界点位置l(或r)
代码模板：
int binarysearch_2(int l,int r){
while(l<r){
int mid=(l+r+1)/2;//需要加1，避免边界问题
if(check(mid)) l=mid;
else r=mid-1;
}
return l;
}（AcWing 789.数的范围）
根据上述思想和模板，代码思路为：
对于模板一，check条件为x<=a[mid]，mid=(l+r)/2，满足条件时x在mid左侧，更新r=mid，最终输出为起始位置
对于模板二，check条件为x>=a[mid]，mid=(l+r+1)/2，满足条件时x在mid右侧，更新l=mid，最终输出为终止位置
最终依次输出各模板的l(或r)
#include <iostream>
#include <algorithm>
using namespace std;
int n;//数组个数
int a[N];
int m,x;//m为询问个数，x为询问数
int main(){
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
while(m--){
cin>>x;
int l=0,r=n-1;
while(l<r){
int mid=(l+r)/2;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[l]!=x) cout<<"-1 -1"<<endl;//未找到
else{
cout<<l<<" ";//起始位置
int l=0,r=n-1;
while(l<r){
int mid=(l+r+1)/2;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
cout<<l<<endl;//终止位置
}
}
return 0;
}
浮点数二分
主要思想：相比整数二分，浮点数二分无需考虑边界问题，比较简单。当二分的区间足够小时，可以认为已经找到了答案，如当r - l < 1e-6（实际上就是区间长度比较小就近似认为是一个数） ，停止二分；或者直接迭代一定的次数，比如循环100次后停止二分
如问题：给定一个浮点数n，求他的二次方根（三次方根类似 ）
代码思路：使用整数二分中的哪个模板都可。这里使用模板一，check条件为x⇐a[mid]，mid=(l+r)/2，满足条件更新r=mid
注意：r不能取小于1的数（小于1的数开方反而更大）.若x=0.04，取r=x，实际结果应为0.2，但算法会在0~0.04中找答案，无法找出答案，故应令r=max(1,x);
#include <iostream>
#include <algorithm>
using namespace std;
double x;
int main(){
cin>>x;
double l=0,r=max(1,x);
while(l<r){
int mid=(l+r)/2;
if(mid*mid >=x) r=mid;
else l=mid;
}
cout<<l;
return 0;
}