算法13、基础二分查找的应用（木根切割等）

🌰1、方程求根

晴问算法

  1️⃣即求f(x) = x^3 + x^2 + x - a = 0的根，又因为要求精确到0.01，所以eps至少设置为1e-3或者更小；

  2️⃣求导得3x^2 + 2x + 1 = 2x^2 + x^2 + 2x + 1 = 2x^2 + (x+1)^2  > 0， 所以f(x)是单调递增函数；

  3️⃣估计查找区间初值：因为a的取值区间是-100-100，所以我们让查找区间的初值为【-100 ， 100】

这样一定能包含所有可能的解。

  对于闭区间【left, right]:

        若f(mid) > 0,说明mid比解大，则让right = mid;

        若 < 0, 说明mid比解小，则让left = mid;

  当right - left <= eps 则可跳出循环。返回left or mid， 即进入循环条件是right-left > eps，最终取两位小数输出

#include <iostream>
using namespace std;
const double EPS = 1e-3;//
int a;
double f(double x){
    return x*x*x + x*x + x -a ;
}
double binarySearch() {
    double left = -100, right = 100, mid;
    while (right - left > EPS) {
         mid = (left + right) / 2;
        if (f(mid) > 0) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return left;//or mid,但是运行时间会更长。
}

int main() {
    cin >> a;
    printf("%.2f", binarySearch());
    return 0;
}

 🌰2、装水问题

晴问算法

1️⃣我们要求h,所以应当对h进行二分查找，又要求精确到2位小数，所以eps至少是1e-3;

2️⃣又显然随着h的增大，s1的面积也增大，所以当我们对h进行二分查找时，

        若s1/s2 > r说明s1过大了，应该缩小右边界，即让right = mid;

        若s1/s2 < r说明s1过小了，应该扩大左边界，即让left = mid;

当right - left <= eps，就找到了满足要求的解，跳出循环。返回左边界。输出带前2位小数的格式。

3️⃣二分查找区间的初值应该是[0, R], 因为它覆盖了h所有可能的取值。

为了统一代码，我们定义函数f(R, h) = s1/s2

#include <cstdio>
#include <cmath>
const double EPS = 1e-3;
const double PI = acos(-1.0);
double f(double R, double h) {
    double alpha = 2 * acos((R - h) / R);
    double L = 2 * sqrt(R * R - (R - h) * (R - h));
    double S1 = alpha * R * R / 2 - L * (R - h) / 2;
    double S2 = PI * R * R / 2;
    return S1 / S2;
}
double binarySearch(double R, double r){
    double left = 0, right = R, mid;
    while(right - left > EPS){
        mid = (left + right) / 2;
        if(f(R, mid) > r)
            right = mid;
        else
            left = mid;
    }
    return left;
}
int main(){
    int R;
    double r;
    scanf("%d%lf", &R, &r);
    printf("%.2lf\n", binarySearch(R, r));
}

🌰3、木棒切割问题

晴问算法

做法1-转化为基础二分查找

对切割后的长度l进行二分查找，设k为长度l下可得到的最大段数。

  转化思路：

        要求得到的段数至少K段，那么求最大长度也就是求：最后一个满足k>=K的length，再转化一下，就是求：第一个满足k<K的length, 再减1。这样就可以运用基础二分查找的思路找到第一个满足k<K的length了：

对于二分查找区间[left, right]:

        若k < K,说明mid有可能是解，但还需往左寻找，因为要求第一个满足k<K的length，那就让right = mid;

        若k >= K, 说明k过大，也就是length过小，那么就让left = mid + 1;

当left == right则找到了解，所以进入循环的条件是left < right.

  ⚠️除数不能为0:

  二分查找区间的初值本应该是[0, max(a[i]) ]，即若返回值是0（0-1==-1）或者1（1-1==0），都说明无法达成，都应该输出0，所以应该额外判断返回值为0时，直接输出0不要再-1了。

  但是，由于计算当前mid可得到的最大段数用到了除法，除数length不能为0，

  因此，查找区间的初值应该从1开始，保证除数不会为0，即left应初始化为1.这样，最后就能够统一输出返回值-1，不需要额外判断返回值了。

返回left or right,最后将返回值-1得到最终结果。

#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN];//存木棒长度
int n, K;
int Num(int length){
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += a[i] / length;//注意除法要求除数不为0！！
    return ans;
}
int binarySearch(int right){
    int left = 1, mid;
    while(left < right){
        mid =  (left + right ) / 2;
        if(Num(mid) < K)
            right = mid;
        else 
            left = mid + 1;
    }
    return left;// or right;
}
int main(){
    cin >> n >> K;
    int maxL = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(a[i] > maxL)
            maxL = a[i];
    }
    printf("%d\n", binarySearch(maxL)-1 );
}

做法2

  1️⃣题目要求切割后每根木棒的最大长度，那么就应该对切割后每根木棒的长度进行二分查找，那么查找区间初值为[0,max(木棒长度)]

  2️⃣又显然，要求切割后得到的木棒段数越多即k越大，长度就会越小，设函数Num(l)为长度为l时可得到的最多段数

对于二分查找区间[left, right]:

        若Num(mid) < k, 不满足至少k段的条件，说明mid不可能是解，且应该让k大一些，那就应该让mid小一点，即让right = mid -1;

        若Num(mid) >= k,满足至少k段的条件，说明mid有可能是解，但还需让mid大一点继续往右检查看是否还有更长的mid满足至少k段，那就让left = mid;

当left == right说明找到了最大长度即解，因此进入循环的条件应该是left < right;

最终应该返回left或者right;

Num(int length) = a1 / length + a2 / length + ……

注意，计算mid时，为了防止left=0,right=1时, 此时mid==0进入Num函数导致的除数为0，应该在此加上1再除以2，

        而且，若没加上1时，当right = left + 1时，设此时left = x, 那么mid = (left + right) /2会等于left==x, 若此时num(mid) >= k那么left = mid == x, 进入下一个循环又是mid=left==x, mid,left就会一直相等num(mid)结果一直不变导致死循环。

#include <iostream>
using namespace std;
const int MAXN = 1005;
int a[MAXN];//存木棒长度
int n, k;
int Num(int length){
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans += a[i] / length;//注意除法要求除数不为0！！
    return ans;
}
int binarySearch(int right){
    int left = 0, mid;
    while(left < right){
        mid =  (left + right + 1) / 2;
        if(Num(mid) < k)
            right = mid - 1;
        else 
            left = mid;
    }
    return left;// or right;
}
int main(){
    cin >> n >> k;
    int maxL = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(a[i] > maxL)
            maxL = a[i];
    }

    printf("%d\n", binarySearch(maxL));
}