二分

二分查找

1、整数二分：

模板：

while (l < r)       //当l >= r 时，遍历结束，停止循环
{
	int mid = (l + r) >> 1;
	if (q[mid] >= x) r = mid;   //check函数 当这个点，大于等于x，说明答案在左边，从右边缩小范围
	else l = mid + 1;   //反之，答案在右边，从左边缩小范围
}

 while (l < r)
{
	if (q[mid] <= x) l = mid;   //check函数，当这个点，小于等于x时，答案在右边，从左边缩小范围
	else r = mid - 1;   //反之，答案在左边，从右边缩小范围
}

2、小数二分

模板：

double eps; //一般比题目要求多两位

while (r - l > eps)  //只要 r - l 不小于该大小，就不断进行二分，找值
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }