二分溢出的问题（二分传统模板的改进）

我们在二分的时候通常是这样的

int bsearch(int l ,int r)
{
	while (l < r)
    {
        int mid = l + r >> 1;   // mid = l + r + 1 >> 1;
        if(check(mid)) r = mid; // l = mid;
        else l = mid + 1;		// r = mid - 1;
    }
    return l;
}

但是当l和r很接近且r很大的时候就可能会导致数据的溢出从而产生错误的划分

改进版本：

int bsearch(int l ,int r)
{
	while (l < r)
    {
        int mid = l + (r - l) >> 1; 	// mid = l + (r - l + 1) >> 1;
        if(check(mid)) r = mid; 		// l = mid;
        else l = mid + 1;				// r = mid - 1;
    }
    return l;
}

本质上就是做等价变形，但是可以避免溢出

二分溢出的问题（二分传统模板的改进）

原文：https://www.cnblogs.com/initlist/p/15140492.html