【BUG 弹药库】二分模板的优化

1. 为什么要优化二分算法？

① 平常学习的二分整数的算法模板边界的问题很容易出错，不知道什么时候用 l = mid，r = mid - 1；或者是 r = mid，l = mid + 1，这两个地方很容易出错，所以要进行优化；

2. 如何去优化原来的二分模板？

• 优化后的代码模板如下：

int l = -1, r = n;		// 注意：将二分查找的下标控制在 [0, n-1]

while (l + 1 != r)
{
		int mid = (l + r) / 2;
		
		if (IsBlue(mid))		// IsBlue()该函数根据具体逻辑进行编写
			l = mid;
		else 
			r = mid;
}
	// 具体返回 l 还是 r 根据你的蓝红边界的划分来确定
	return l or r;
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 案例分析

• 实际的举例：
  
  
  
• 二分模板的流程