二分查找

Posted by 磊落 on May 11, 2020

二分查找

整数二分

特点

  • 单调序列一定可以二分查找，但二分查找不一定是单调序列

  • 整数二分，有两套模板

  • 二分是一定会得到一个答案的，一定有解。 但是这个解不一定是满足题目要求，题目可能是无解的。

  • 当区间内只有一个值时就是二分的结果。 二分一定有结果，但结果不一定满足题目

  • 确保最后结果落在只包含一个元素的区间。 即确保通过二分最后结果为一个确定的值，不能是一个区间。（整数二分的特点）

思想

第一套模板

    int mid = l + r + 1 >> 1 //注意当 l = mid 则必须加1, 因为当 l = r - 1 时，如果不加1，则 l + r >> 1 依旧为 l, 那么 l = mid 仍然是 [l, r] 循环完区间没有发生变化，会导致死循环。 
    if (check(mid))
        l = mid
        [mid, r]  //待求整数在区间[mid, r]中
    else
        r = mid - 1
        [l, mid - 1] //待求整数在区间[l, mid - 1]中

第二套模板

    int mid = l + r >> 1
    if (check(mid))
        r = mid
        [l, mid] // 待求整数在区间[l, mid]中
    else
        l = mid + 1
        [mid + 1, r] //待求整数在区间[mid + 1, r]中

核心思想： 写一个check(mid)函数，判断是l = mid 还是 r = mid

当二分查找不存在这个数的时候，返回数组中第一个大于等于这个数的值

#include <iostream>
#include <algorithm>

using namespace std;


int main()
{




    return 0;
}

浮点数二分

特点

  • 不涉及整数二分的边界加减问题

思想

  • 同整数二分类似，最后要保证二分的区间越来越小

求平方根

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    double x;
    cin >> x;

    double l = 0, r = x;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid <= x) l = mid;
        else r = mid;
    }

    cout << l << endl;
    return 0;



}
FEATURED TAGS