Acwing 二分

1.整数二分

二分的本质不是单调性，有单调性一定可以二分，可以二分不一定有单调性 二分的本质是边界，假设给定一个区间，如果能够根据某个条件，将区间划分为左右两部分，使得左半边满足这个条件，右半边不满足这个条件（或者反之）。就可以用二分来查找左右两部分的边界点。

主要思想：假设这组数据关键字已经有序
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 799.数的范围

根据上述思想和模板，代码思路为：

对于模板一，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;

const int N = 100010; // 定义数组最大大小

int a[N]; // 定义数组，用来存储输入的元素
int n, m; // n 表示数组大小，m 表示查询次数

int main() {
    // 输入 n 和 m，分别表示数组大小和查询次数
    cin >> n >> m;
    
    // 输入数组中的 n 个元素
    for (int i = 0; i < n; i++) 
        cin >> a[i];
    
    // 处理每次查询
    while (m--) {
        int x; // 待查找的目标值 x
        cin >> x;

        // 二分查找，找 x 的起始位置
        int l = 0, r = n - 1; // 初始化左右边界 l 和 r
        while (l < r) { // 通过二分查找不断缩小范围
            int mid = (l + r) / 2; // 计算中间位置 mid
            if (a[mid] >= x) // 如果中间值大于等于 x，目标值可能在左侧（包括 mid）
                r = mid; // 收缩右边界
            else 
                l = mid + 1; // 否则目标值在右侧，移动左边界
        }

        // 检查是否找到目标值，如果数组中 l 位置的元素不等于 x，说明没找到
        if (a[l] != x) 
            cout << "-1 -1" << endl; // 输出 -1 -1 表示没找到
        else {
            
            cout << l << ' '; // 起始位置输出
            
            // 二分查找，找 x 的终止位置
            int l2 = 0, r2 = n - 1; // 使用新的左右边界 l2 和 r2
            while (l2 < r2) {
                // 这里 mid 计算公式稍有不同，使用 (l2 + r2 + 1) / 2 可以避免死循环
                int mid = (l2 + r2 + 1) / 2;
                if (a[mid] <= x) 
                    l2 = mid; // 如果中间值小于等于 x，目标值可能在右侧，移动左边界
                else 
                    r2 = mid - 1; // 否则移动右边界
            }
            
            cout << l2 << endl; // 输出终止位置
        }
    }

    return 0; // 程序正常结束
}

2.浮点数二分

主要思想：相比整数二分，浮点数二分无需考虑边界问题，比较简单。当二分的区间足够小时，可以认为已经找到了答案，如当r - l < 1e-6（实际上就是区间长度比较小就近似认为是一个数） ，停止二分；或者直接迭代一定的次数，比如循环100次后停止二分

如问题（Acwing 790）：给定一个浮点数n，求他的二次方根（三次方根类似 ）

代码思路：使用整数二分中的哪个模板都可。这里使用模板一，check条件为x<=a[mid]，mid=(l+r)/2，满足条件更新r=mid

• 初始区间为 [-10000, 10000]，用 l 和 r 表示左边界和右边界；
• 当 r - l <= 1e-8 时，即误差小于 1e-8，循环停止，结果接近输入 x 的立方根。

具体实现代码（详解版）：

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    double x;
    cin >> x;
    double l = -10000, r = 10000;
    while(r - l > 1e-8){
        double mid = (l + r ) / 2;
        if(mid * mid * mid >= x) r = mid;//mid偏大，更新右边界
        else l = mid ;//mid偏小，更新左边界
    }
    printf("%lf",l);
    return 0;
}

总结：二分查找（Binary Search） 是一种高效的查找算法，常用于在 有序数组 中查找某个元素的位置。其核心思想是 逐步减半，通过比较目标值与中间值的大小，缩小查找范围，最终找到目标值或确定其不存在

原文地址：https://blog.csdn.net/qq_43060884/article/details/142874296

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！