整数与浮点数二分算法

整数与浮点数二分算法 2023-04-08 653

整数二分

作用为：利用二分搜索的思想。来找到一个数特殊数的左右边界。

例如： {1，2，3，3, 4，5，8，10}

找到值为3的左边界序号为1，右边界序号3。如何找到左右边界呢.

发现， 3的左边是小于等于3的（性质1）且 3的右边是大于等于3的（性质2）

步骤

## 模板

int x;//目标值
// 查找左边界
//查找大于等于/大于key的第一个元素
int bsearch_1(int l, int r)
{
          
   
    while (l < r)
    {
          
   
        int mid = l + r >> 1; //等于（l+r）/2
        if (a[mid]<x) l = mid+1; //目标值在区间左边，包括mid
        else r = mid;//目标值在区间右边
    }
    return l;
}
// 查找右边界
//查找大于等于key的最后一个元素
int bsearch_2(int l, int r)
{
          
   
    while (l < r)
    {
          
   
        int mid = l + r + 1 >> 1; //等于（l+r+1）/2
        if (a[mid]>x) r = mid - 1; //目标值在区间左边
        else l = mid;//目标值在区间右边，包括mid
    }
    return l;
}

二分模板题

https://www.acwing.com/problem/content/791/

浮点数二分

不用考虑边界。循环条件终止有两个循环100次。相当于 / 2^n r - l > eps // eps 表示精度，取决于题目对精度的要求

模板

bool check(double x) {
          
   /* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
          
   
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
          
   
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

或者

bool check(double x) {
          
   /* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
          
   
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    for(int i = 1; i<= 100 ; i++)
    {
          
   
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}