[基础算法](2)二分

二分搜索

引言:

第一篇二分搜索论文是 1946 年发表,然而第一个没有 bug 的二分查找法却是在 1962 年才出现,中间用了 16 年的时间。
——不知道哪里看的

核心思路:

  • 对比中值
  • 根据中值与目标值的对比收缩区间
  • 查询区间需具有单调性

二分查找算法模板 - AcWing

学习二分最好方法,记一个好用的模板,再理解二分的思路,然后根据思路去模板做调整

模板题:789. 数的范围 - AcWing题库

image-20210708163814817

代码:

//做二分题最好的方式是在纸上模拟一边思路
#include<stdio.h>
#include<stdlib.h>
#define N 100010
int nums[N];
int n, m;

int Bsearch_left(int x, int l, int r) {
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] >= x) r = mid;//不断缩小右边界靠近目标值
        else l = mid + 1;
    }
    return l;
}
int Bsearch_right(int x, int l, int r) {
    while (l < r) {
        int mid = ((l + r) / 2) + 1;
        if (nums[mid] <= x) l = mid;//不断缩小左边界靠近目标值
        else r = mid - 1;
    }
    return l;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%d", &nums[i]);

    while (m--) {
        int x;
        int a = -1, b = -1;
        scanf("%d", &x);
        a = Bsearch_left(x, 0, n - 1);
        if (nums[a] != x) printf("-1 -1\n");//若左边最后一个大于等于目标值的元素不存在,则输出-1 -1
        else {
            b = Bsearch_right(x, 0, n - 1);
            printf("%d %d\n", a, b);
        }
    }
    return 0;
}

浮点数二分

浮点数二分没得边界条件要考虑,所以简单很多,直接套模板即可

模板题:790. 数的三次方根 - AcWing题库

image-20210708165616980

代码:

#include<iostream>
using namespace std;
int main() {
    double x;
    cin >> x;
    double l = -100, r = 100;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid*mid*mid>=x)r = mid;
        else l = mid;
    }
    printf("%.6lf", l);
    return 0;
}

本文链接:

https://nullcode.fun/159.html
1 + 7 =
快来做第一个评论的人吧~