模板一 （右合法 [l,r]——>[l,mid] [mid+1,r]
int search_1(int l,int r){ while(l<r){ int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } return l; }模板二 （左合法 [l,r]——>[l,mid-1] [mid,r] 计算mid时要加1
int search_2(int l,int r){ while(l<r){ int mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } return l; }`模板三（实数的话 [l,r]——>[l,mid] [mid,r]
while(r-l>=1e-7){ mid=(l+r)/2;//注意不能用位运算了 if(check(mid)) r=mid; else l=mid; }能二分的题一定是满足某种性质，分成左右两部分； if的判断条件是让mid落在满足你想要结果的区间内； ☆☆☆判断是左合法还是右合法
No.1 789. 数的范围 判断第一次出现是右合法，if里面应该是a[mid]>=x； 判断第二次出现是左合法，if里面应该是a[mid]<=x； 注意啦注意啦！！！不要忘记=号！！！
#include<bits/stdc++.h> using namespace std; int main(){ int n,q,x; cin>>n>>q; int a[100100]; for(int i=0;i<n;i++){ cin>>a[i]; } while(q--){ cin>>x; int l=0,s=n-1,mid; //第一次出现，右合法 while(l<s){ mid=l+s>>1; if(a[mid]>=x) s=mid; else l=mid+1; } if(a[l]!=x){ cout<<"-1"<<" "<<"-1"<<endl;continue; } else cout<<l<<" "; l=0;s=n-1; //最后一次出现，左合法 while(l<s){ mid=l+s+1>>1; if(a[mid]<=x) l=mid; else s=mid-1; } cout<<l<<endl; } return 0; }No.2 LeetCode 69.x的平方根
#include<bits/stdc++.h> using namespace std; int mySqrt(int x) { int l = 0, r = x; while (l < r) { // 两个int相加减会溢出 中间加个长整型常量 // 少用乘法，用除法可以防止溢出 int mid = l + 1ll + r >> 1; if (mid <= x / mid) l = mid;//左合法 else r = mid - 1; } return l; } int main(){ int x; cin>>x; cout<<mySqrt(x); //由于返回类型是整数，小数部分被舍弃 return 0; }No.3 790 数的三次方根
#include<iostream> #include<iomanip> using namespace std; double n,l,r,mid; bool flag; double q(double a){return a*a*a;} int main(){ cin>>n; l=-10000,r=10000; while(r-l>=1e-7){ mid=(l+r)/2; if(q(mid)>=n) r=mid; else l=mid; } cout<<fixed<<setprecision(6)<<l; return 0; }No.4 1227. 分巧克力 找到满足条件的左端的最大值—左合法 if里面 mid越大，p(mid)越小，即块数越少
#include<bits/stdc++.h> using namespace std; int n,k; int a[100100],b[100100]; int p(int mid){ int sum=0; for(int i=0;i<n;i++){ sum+=(a[i]/mid)*(b[i]/mid); } return sum; } int main(){ cin>>n>>k; for(int i=0;i<n;i++){ cin>>a[i]>>b[i]; } int l=1,r=100000;//枚举边长 while(l<r){ int mid=l+r+1>>1; if(p(mid)>=k) l=mid;//左合法 else r=mid-1; } cout<<l; return 0; } ``