二分法

二分法是一种在一类单调的问题中快速寻找答案的方法，复杂度为O(logn)。

while(left < right){
        int mid = left + (right - left)/2;     //也可也写成(left+right)>>1
        if(check(mid)){       
            ans = mid;        
            left = mid + 1;  
           }
        else
            right = mid;//特定题目可以写成right = mid - 1
}

整数二分
例
①找单调函数的解，即f(x) = 0的零点。如果存在零点，那么在零点两端必然有两点a,b使得f(a)*f(b) < 0。不断的枚举中点即可。
②寻找某个数。应用：在数组中寻找指定和sum的整数对。那么枚举a[i]，在剩余的数中二分查找sum-a[i]的数是否存在。
③最小值最大化。
例题：有一个序列{2,2,3,4,5,1}，将其划分成3个连续的子序列S(1)、S(2)、S(3)，每个子序列最少有一个元素，要求使得每个子序列的和的最大值最小。
枚举每一个x，用贪心法每次从左向右尽量多划分元素，S(i)不能超过x，划分的子序列个数不超过m个。这个方法虽然可行，但是枚举所有的x太浪费时间了，因此用二分优化，枚举最大值x。
例题2：洛谷P2678
有许多石头，可以移走某些石头使得跳跃距离增加。想要求这些石头最短距离最大，且移走的石头数小于x。二分枚举最短距离，若在该枚举范围内的石头则移除，最后验算是否满足移走的石头数小于x即可。
④最大化最小值。
例题1：洛谷P1462
https://blog.csdn.net/qq_42937838/article/details/108953467
求经过的点权最大值最小。用二分法枚举最大值的上界即可。
习题：
饥饿的奶牛　　https://www.luogu.org/problem/P1868

寻找段落　　　https://www.luogu.org/problem/P1419

小车问题　　　https://www.luogu.org/problem/P1258

借教室　　　　https://www.luogu.org/problem/P1083

跳石头　　　　https://www.luogu.org/problem/P2678

实数二分

const double eps =1e-7;        //精度。如果下面用for，可以不要eps
while(right - left > eps){     //for(int i = 0; i<100; i++){如果用for循环，由于循环内用了二分，执行100次，相当于实现了 1
    /2100的精度，一般比eps更精确。
      double mid = left+(right-left)/2;
      if (check(mid)) right = mid;           //判定，然后继续二分
      else            left  = mid;
}

例题：http://poj.org/problem?id=3122

关于STL的lower_bound和upper_bound
（1）查找第一个大于x的元素的位置：upper_bound()。代码例如：
　　　　　pos = upper_bound(a, a+n, test) - a;
（2）查找第一个等于或者大于x的元素：lower_bound()。
（3）查找第一个与x相等的元素：lower_bound()且 = x。
（4）查找最后一个与x相等的元素：upper_bound()的前一个且 = x。
（5）查找最后一个等于或者小于x的元素：upper_bound()的前一个。
（6）查找最后一个小于x的元素：lower_bound()的前一个。
（7）单调序列中数x的个数：upper_bound() - lower_bound()。

int cmp(int a,int b){
    return a>b;
}
int main(){
    int num[6]={1,2,4,7,15,34}; 
    sort(num,num+6);                           //按从小到大排序 
    int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 
    int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值
    cout<<pos1<<" "<<num[pos1]<<endl;
    cout<<pos2<<" "<<num[pos2]<<endl;
    sort(num,num+6,cmp);                      //按从大到小排序
    int pos3=lower_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于或等于被查数的值 
    int pos4=upper_bound(num,num+6,7,greater<int>())-num;  //返回数组中第一个小于被查数的值 
    cout<<pos3<<" "<<num[pos3]<<endl;
    cout<<pos4<<" "<<num[pos4]<<endl;
    return 0;   
}

三分法
是在凸函数（上凸或下凸）上找极值的搜索方法。
（1）若f(mid1) < f(mid2)，极值点v一定在mid1的右侧。此时，mid1和mid2要么都在v的左侧，要么分别在v的两侧。
图片说明
（2）若f(mid1) > f(mid2)，极值点v一定在mid2的左侧。

图来自https://blog.csdn.net/weixin_43914593/article/details/103250854

  mid1和mid2的取法有两种。
 ①三等分：mid1和mid2为[l, r]的三等分点。那么区间每次可以减少三分之一。
 ②近似三等分：计算[l, r]中间点mid = (l + r) / 2，然让mid1和mid2非常接近mid，例如mid1 = mid - eps，mid2 = mid + eps，其中eps是一个很小的值。那么区间每次可以减少接近一半。

while(R-L > eps){  // for(int i = 0; i<100; i++){   //三等分
        double k =(R-L)/3.0;
        double mid1 = L+k, mid2 = R-k;
        if(f(mid1) > f(mid2)) 
               R = mid2;
        else   L = mid1;
    }

while(R-L > eps){   // for(int i = 0; i<100; i++){   //近似三等分。有精度风险
        double mid = L+(R-L)/2; 
        if(f(mid - eps) > f(mid))
             R = mid;
        else L = mid;
     }

模板例题:https://www.luogu.com.cn/problem/P3382

参考博客：https://blog.csdn.net/weixin_43914593/article/details/103250854

二分法 三分法

二分法

实数二分

二分法三分法