结合时间复杂度浅谈二分法的好处(将持续更新,绝对值你一个收藏)

前言

笔者虽然刷的算法题不多,但是笔者也敢说,二分法真的是一种很优越的算法,使用上限极高的那种,正因如此,笔者才想浅谈一下二分法.

封面是我很喜欢的一个游戏角色,不知道有没有老gal玩家知道!

什么是二分法?

枚举查找即顺序查找，实现原理是逐个比较数组 a[0:n-1] 中的元素，直到找到元素 x 或搜索整个数组后确定 x 不在其中。最坏情况下需要比较 N 次，时间复杂度是 O(n)，属于线性阶算法。

而二分查找是一种折半查找方法。该方法将 N 个元素分成大致相等的两部分，选取中间元素与查找的元素进行比较。如果相等，则查找成功；如果查找元素小于中间元素，则在左半区继续查找；如果查找元素大于中间元素，则在右半区继续查找。每次都将范围缩小至原来的一半，因此时间复杂度是 O(log2n)。需要注意的是，二分查找的前提是数组有序，一般是从小到大排列。

相信大家伙学c语言的时候就接触过了,笔者上一行代码给大家看看

C++ 版本

// C++  的版本
while (low < high)
{
    int mid = (low + high) / 2;
    if (a[mid] >= x)
        high = mid;

    else
        low = mid + 1;
}

while (low < high)
{
    int mid = (low + high + 1) / 2;

    if (a[mid] <= x)
        low = mid;

    else
        high = mid - 1;
}

java版本


while (low < high) {

    int mid = (low + high) / 2;

    if (a[mid] >= x)
      high= mid;

  else
      low = mid + 1;
}

while (low < high) {

    int mid = (low + high + 1) / 2;

    if (a[mid] <= x)
      low = mid;

  else
      high = mid - 1;

}

看得出来,真的没什么区别(哈哈哈!) 毕竟语言有界,算法无界!

时间复杂度

接下来,我们来分享它的时间复杂度

所谓时间复杂度,说白了,就是一个代码算法执行的次数

那么二分的时间复杂度怎么算?

答:O(log2n)

如图所示(有点丑别介意)

我们假设最坏情况,需要查询(执行)y次才能找到我们要的数,那么每次都是二分,2^y 就能代表总数N,所以执行y=log2n 即时间复杂度为O(log2n)

与n相比O(log2n) 不就是很大的提升了吗?

刚刚分享的是二分整数,还有精度较高的写法,以下代码来自

风骨散人Chiam-CSDN博客

我也上过这位老师的课,给大家推荐下!!!!

//模版一：实数域二分，设置eps法

//令 eps 为小于题目精度一个数即可。比如题目说保留4位小数，0.0001 这种的。那么 eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。

//一般为了保证精度我们选取精度/100 的那个小数，即设置 eps= 0.0001/100 =1e-6

while (l + eps < r)
{
    double mid = (l + r) / 2;

    if (pd(mid))
        r = mid;
    else
        l = mid;
}

//模版二：实数域二分，规定循环次数法
//通过循环一定次数达到精度要求，这个一般 log2N < 精度即可。N 为循环次数，在不超过时间复杂度的情况下，可以选择给 N 乘一个系数使得精度更高。

    for (int i = 0; i < 100; i++)
{

    double mid = (l + r) / 2;
    if (pd(mid))
        r = mid;
    else
        l = mid;
}

部分题目分享

笔者接下来分享写过的两个题目

题目一 —— 来自蓝桥的计算方程

11.计算方程【算法赛】 - 蓝桥云课 (lanqiao.cn)

给大家伙看看题目

计算机又不会解方程,那我们咋办嘛?

就好比高中的选择压轴题,我们套答案!

怎么套! 一个个列举呗

怎么列举?难道从1开始一个个去列举吗?那要什么时候列举的出来?

那咋办吗? 这个时候就需要二分了,找到适合的答案,且以较低的复杂度

C++

#include <iostream>
#include <cmath>

#define ll long long

int k, m;

int check(int x)
{
    if (sqrt(x) + floor(log(x) / log(k)) - m > 0)
        return 1;
    return 0;
}

void solve()
{
    std::cin >> k >> m;
    int l = 1, r = 1000000000;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    std::cout << l << std::endl;
}

int main()
{
    int t;
    std::cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

Java

import java.util.Scanner;

public class Main {

    static int k, m;

    static int check(int x) {
        if (Math.sqrt(x) + Math.floor(Math.log(x) / Math.log(k)) - m > 0)
            return 1;
        return 0;
    }

    static void solve() {
        Scanner scanner = new Scanner(System.in);
        k = scanner.nextInt();
        m = scanner.nextInt();
        int l = 1, r = 1000000000;
        while (l < r) {
            int mid = (l + r) / 2;
            if (check(mid))
                r = mid;
            else
                l = mid + 1;
        }
        System.out.println(l);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            solve();
        }
        scanner.close();
    }
}

套公式走