实数二分

在了解实数二分之前，应先了解整数二分。

一、思路

• 将区间$[L, R]$划分成$[L, M]$和$[M, R]$。
• 在$while$循环中，如果$ans$在$[M, R]$，那么$L=M$；否则$ans$在$[L, M]$，那么$R=M$。
• $while$循环的表达式为$R-L>eps$，我们通常把$eps$设为题目要求的范围的$100$分之一，如保留$6$位小数，则$eps=1e-8$。

---

二、模板

while(R - L > 1e-6) {
	double M = (L + R) / 2;
	if (check()) L = M;
	else R = M;
}

---

三、模板题

Acwing AcWing 790. 数的三次方根

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

int main() {
    double x;
    cin >> x;
    double l = -1000, r = 1000;
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%f", l);
    return 0;
}