整数二分算法和浮点数二分算法

整数二分算法和浮点数二分算法

二分

现实中运用到二分的就是猜数字的游戏 假如有A同学说B同学所说数的大小，B同学要在1~100中间猜中数字65，当B同学每次说的数都是范围的一半时这就算是一个二分查找的过程

二分查找的前提是这个数字序列要有单调性

基本步骤

初始化：

设定两个指针，left 和 right，分别指向数组的起始和末尾。

计算中间位置：

使用公式 mid = left + (right - left) / 2 或者left+right>>1计算中间位置。

比较：

如果中间位置的元素等于目标值，返回中间位置。
如果目标值小于中间位置的元素，则将 right 更新为 mid - 1，继续在左半部分查找。
如果目标值大于中间位置的元素，则将 left 更新为 mid + 1，继续在右半部分查找。

重复：

重复步骤 2 和 3，直到 left 超过 right。

结束：

如果在查找过程中未找到目标值，返回一个表示未找到的结果（如 -1 或 None）。

二分查找算法的时间复杂度是 O(log n)，非常高效。

整数二分

二分的本质并不是一定要单调，而是对一个区间可以化分成两个部分，一部分一定满足条件，另一部分一定不满足，对于满足这种条件的我们可以找出两个边界点，这样的话二分算法可以寻找这个性质的边界（红色和黑色的边界都行，因为是整数二分所以两边界不重合）。

第一种情况（二分左半部分）

假如说有一串数字1，2，3，3，4，4，5，6，8，8我们需要找到满足小于等于3的最大情况的子序列，也就是我们需要找到最后一次出现的3，我们可以如何做呢？
我们让一个mid=(l+r+1)/2 假如说a[mid]<=3,此时if(check(mid))==true说明此时mid指向的值可能是答案，但是我们无法保证其后面还有没有答案是<=3的，所以此时应该是l=mid,假如说此时a[mid]>=3,if(check(mid))==false说明此时mid指向的是一定不满足条件的的那么此时应该是r=mid-1。

我们继续不段重复以上操作直到l>=r时退出循环。

第二种情况(二分右半部分)

还是这个数字序列这次我们要找1，2，3，3，4，4，5，6，8，8中第一次出现3的位置，我们应该怎么做呢？
我们还是让一个mid=(l+r)/2 假如说a[mid]>=3,此时if(check(mid))==true说明此时mid指向的值可能是答案，但是我们无法保证其前面还有没有答案是>=3的，所以此时应该是r=mid,假如说此时a[mid]<=3,if(check(mid))==false说明此时mid指向的是一定不满足条件的的那么此时应该是l=mid+1。

注意：第一种情况是（l+r+1）而不是（l+r）为为什么呢？

因为计算机的除法都是向下取整的所以就会出现问题，假如说此时l=r-1那么mid=(l+r)/2=(l+l+1)/2=l然后我们假如发现l还是满足条件的，那么此时就会陷入l=mid,mid=l的死循环

我们来写一道题

洛谷P2249
下面的代码是既有第一次出现，也有最后一次出现的，两种情况都写了。
代码如下：

#include <iostream>
using namespace std;

const int N = 1e5 + 10; // 定义数组的最大容量，数组a最多可以存放1e5个元素
int a[N], n, m; // 定义全局变量数组a，n为数组长度，m为查询次数

// check1函数用于检查a[mid]是否大于等于目标值x
bool check1(int mid, int x) {
    if (a[mid] >= x) {
        return true; // 如果a[mid]大于等于x，返回true，表示满足条件
    } else {
        return false; // 否则返回false，表示不满足条件
    }
}

// check2函数用于检查a[mid]是否小于等于目标值x
bool check2(int mid, int x) {
    if (a[mid] <= x) {
        return true; // 如果a[mid]小于等于x，返回true，表示满足条件
    } else {
        return false; // 否则返回false，表示不满足条件
    }
}

int main() {
    cin >> n >> m; // 输入数组的长度n和查询的次数m
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; // 依次输入数组a的元素
    }

    while (m--) { // 对每一次查询进行处理，m次查询
        int x; // 定义要查询的目标值x
        cin >> x; // 输入目标值x
        
        // 首先进行二分查找，寻找第一个大于等于x的位置
        int l = 1, r = n; // 初始化左右边界，l是左边界，r是右边界
        while (l < r) { // 当左边界小于右边界时，继续二分查找
            int mid = (l + r) >> 1; // 计算中间位置mid
            if (check1(mid, x)) { // 如果a[mid]大于等于x
                r = mid; // 缩小右边界至mid
            } else {
                l = mid + 1; // 否则缩小左边界至mid+1
            }
        }

        // 查找完成后，检查a[l]是否等于目标值x
        if (a[l] == x) {
            cout << l << " "; // 如果a[l]等于x，输出位置l
        } else {
            cout << -1 << " "; // 如果a[l]不等于x，输出-1表示未找到
        }

        // 再进行一次二分查找，寻找最后一个小于等于x的位置
        l = 1, r = n; // 重新初始化左右边界
        while (l < r) {
            int mid = (l + r + 1) >> 1; // 计算中间位置mid，向上取整
            if (check2(mid, x)) { // 如果a[mid]小于等于x
                l = mid; // 缩小左边界至mid
            } else {
                r = mid - 1; // 否则缩小右边界至mid-1
            }
        }

        // 查找完成后，再次检查a[l]是否等于目标值x
        if (a[l] == x) {
            cout << l << " "; // 如果a[l]等于x，输出找到的最后位置l
        } else {
            cout << -1 << " "; // 如果没找到，输出-1
        }
        cout<<endl;
    }
}

整数二分模板

bool check(int x) {
    // 这里是判断x是否满足某种性质的函数，具体实现取决于实际问题
    // 可以根据x的值来返回true或false，用于二分查找中的判断
    /* ... */
}

// 区间[l, r]被划分为[l, mid]和[mid + 1, r]时使用的二分查找
int bsearch_1(int l, int r) {
    // 二分查找的目的是在区间[l, r]中寻找满足某种性质的最小位置
    // l 是左边界，r 是右边界，最终返回满足性质的最小下标
    while (l < r) { // 当左边界小于右边界时，继续进行二分查找
        int mid = (l + r) >> 1; // 计算中间位置mid，使用右移操作进行快速计算，相当于 (l + r) / 2
        if (check(mid)) { // 如果check(mid)为true，表示mid满足性质
            r = mid; // 将右边界缩小到mid，因为我们要找满足性质的最小位置
        } else { // 否则，mid不满足性质
            l = mid + 1; // 将左边界缩小到mid + 1，因为mid以及它左边的值都不满足条件
        }
    }
    return l; // 返回最终的左边界，此时l == r，且为满足性质的最小位置
}

// 区间[l, r]被划分为[l, mid - 1]和[mid, r]时使用的二分查找
int bsearch_2(int l, int r) {
    // 二分查找的目的是在区间[l, r]中寻找满足某种性质的最大位置
    // l 是左边界，r 是右边界，最终返回满足性质的最大下标
    while (l < r) { // 当左边界小于右边界时，继续进行二分查找
        int mid = (l + r + 1) >> 1; // 计算中间位置mid，并向上取整，确保mid偏向右侧
        if (check(mid)) { // 如果check(mid)为true，表示mid满足性质
            l = mid; // 将左边界缩小到mid，因为我们要找满足性质的最大位置
        } else { // 否则，mid不满足性质
            r = mid - 1; // 将右边界缩小到mid - 1，因为mid以及它右边的值都不满足条件
        }
    }
    return l; // 返回最终的左边界，此时l == r，且为满足性质的最大位置
}

浮点数二分算法

浮点数二分相较于整数二分更加简单因为只有一个模板，并且没有边界问题，浮点数的二分查找可以用于求解需要精确值的问题，例如求方程的解或几何问题中涉及浮点精度的求解。与整数二分查找不同，浮点数二分查找必须考虑精度问题，因为浮点数无法精确到某个具体值，所以我们需要一个精度（如 epsilon），用于判断二分查找的终止条件。

假如说我们需要找一个数x的平方等于目标值2

代码如下：

#include <iostream>
#include <cmath> // 包含abs函数，用于计算绝对值
using namespace std;

// 定义一个需要使用二分法求解的函数，返回值为目标函数值
double f(double x) {
    // 举例：寻找函数 f(x) = x^2 - 2 的根
    return x * x - 2;
}

int main() {
    double l = 0, r = 2; // 初始区间[l, r]，假设根位于[0, 2]之间
    double eps = 1e-7;   // 定义精度eps，即当结果误差小于1e-7时停止迭代

    // 当区间宽度大于精度要求时，继续二分
    while (r - l > eps) {
        double mid = (l + r) / 2; // 计算中间值
        if (f(mid) > 0) { // 如果 f(mid) > 0，表示 mid 处的值在根的右侧
            r = mid; // 缩小右边界至mid
        } else { // 否则 f(mid) <= 0，表示 mid 处的值在根的左侧或是根
            l = mid; // 缩小左边界至mid
        }
    }

    // 输出结果，l 和 r 最终都会逼近根
    cout << "x ≈ " << l << endl;
    cout << "验证结果: f(x) = " << f(l) << endl; // 输出验证f(l)接近0
}

浮点数二分模板

// 函数原型：在浮点数区间 [l, r] 上使用二分查找，找到满足某种性质的浮点数
double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 是精度控制的参数，当区间长度小于 eps 时停止二分查找
    // 1e-6 表示小数点后 6 位精度，可根据题目要求调整精度

    // 当区间长度大于 eps 时，继续进行二分查找
    while (r - l > eps)
    {
        // 计算区间的中点 mid
        double mid = (l + r) / 2;

        // 调用 check 函数判断 mid 是否满足给定的性质
        // 假设 check(mid) 返回 true，则意味着 mid 及其右侧可能满足性质，
        // 因此将右区间收缩到 mid，继续在左侧区间 [l, mid] 上搜索
        if (check(mid)) 
            r = mid;
        // 否则，mid 及其左侧不满足性质，因此我们将左区间收缩到 mid，继续在右侧区间 [mid, r] 上搜索
        else 
            l = mid;
    }

    // 最后返回左边界 l（或右边界 r），此时区间已经很小，接近于精度要求的结果
    // 因为 l 和 r 的距离非常小，最终答案应为 l 或 r 的近似值
    return l;
}

整数二分算法和浮点数二分算法源代码