二分

只要是有二段性质的问题，都可以二分。

二分一定有解，但是这个解不一定是题目要求的解，因此要在二分得到解后判断这个解是否符合条件。

整数二分问题避免边界问题的一点套路

如果整数二分代码中有： $l = mid$，则此时的$mid$应该是更新为 $mid = l + r + 1$。

浮点数二分不必考虑此边界问题。

二分的代码比较简单，但是题目的二段性可以藏的很深。

一道简单的浮点数二分题：

求数的三次方根

#include <iostream>
using namespace std;

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