二分查找
每次查找的区间在 [left, right] （左闭右闭区间），根据查找区间的定义（左闭右闭区间），就决定了后续的代码应该怎么写才能对。因为定义 target 在 [left, right] 区间，所以有如下两点：
- 循环条件要使用 while(left <= right) ，因为当 (left == right) 这种情况发生的时候，得到的结果是有意义的
- if(nums[middle] > target) ， right 要赋值为 middle - 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是 [left, middle - 1]
代码
//普通二分
int find(int a[],int k)
{
int l,r,mind;
l=1,r=n;
while(l<=r)
{
mid=(l+r)>>1;
if(a[mid]==k)
{
return mid;
}
else if(a[mid]>k)
{
r=mid-1;
}
else
{
l=mid+1;
}
}
return -1;
}
二分答案
求最大值和最小值在求 mid 时 和交换 l 和 r 时这两处有差别
- 求最大值问题
最短距离最大化问题：保证任意区间距离要比最短距离mid大或相等（这样，mid才是最短距离）即：区间的距离>=mid
只要是往右找答案，mid要加一，l=mid，r要减一！！！！
代码
//二分求最大值问题伪代码
#include <bits/stdc++.h>
#define ll long long
#define c const
using namespace std;
int n,x;
c int N=1e7+5;
int a[N];
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=1,r=n;
while(l<r){
int m=(l+r+1)/2;
if(a[m]<=x){
l=m;
}
else if(a[m]>x){
r=m-1;
}
}
cout<<a[r]<<endl;
return 0;
}
-求最小值问题
最长距离最小化问题：保证任意区间距离要比最大距离mid小或相等（这样，mid才是最大距离）即：区间的距离<=mid
只要是往左找答案，mid不用加一，r=mid，l加一！！！！
代码
//二分求最小值问题伪代码
#include <bits/stdc++.h>
#define ll long long
#define c const
using namespace std;
int n,x;
c int N=1e7+5;
int a[N];
int main(){
cin>>n>>x;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int l=1,r=n;
while(l<r){
int m=(l+r)/2;
if(a[m]<x){
l=m+1;
}
else if(a[m]>=x){
r=m;
}
}
cout<<a[r]<<endl;
return 0;
}
- 实数二分
实数二分就相对简单多了，因为浮点除法不会取整，所以mid，l，r，都不用加1或减1.
模板
while(r-l>1e-5) //需要一个精度保证
{
double mid = (l+r)/2;
if(check(mid)) l=mid; //或r=mid;
else r=mid; //或l=mid;
}