二分

简单介绍一下什么是二分

顾名思义，就是把数组的所有元素一分为二，即从中间切开将数组分为两段，通过对比要查找的元素跟中间元素的大小来判断，要查找的元素在哪一段数组中，每次查询便能将数组的查询范围缩短一半。用于大数据的查询时，能够大大的提高查询效率。

二分主要分为两类

• 整数二分
• 浮点数二分

二分主要有两套模版

第一套模版

如果r = mid的话，那么我们计算mid 的时候不用进行加1操作

void binary_search(int x) {
		int l = 1,r = n;
		while(l < r) {
				int mid = (l + r) >> 1;
				if(check(mid)) r = mid;
				else l = mid + 1;
		}
}

第二套模版

如果l = mid的话，我们计算mid 的时候需要加1

void binary_search(int x) {
		int l = 1,r = n;
		while(l < r) {
				int mid = (l + r + 1) >> 1;
       	if(check(mid)) l = mid;
       	else r = mid - 1;
		}
}

浮点数二分

浮点数二分很经典的题目就是求一个浮点数的开N次方问题

如何解决

假如我们开的是3次方，我们需要保证mid * mid * mid尽可能的接近最终的结果，最终判断l 和r是否接近即可

#include <bits/stdc++.h>
using namespace std;

int main(){
    double n;
    cin >> n;
    double l = -100,r = 100;
    while(r - l >= 1e-8) {
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }

    printf("%lf",l);
    return 0;
}