首先,使用二分有几个前提:
-
具有单调性
-
要求“最小的最大”或“最大的最小”
其次,还要分清楚二分查找与二分答案的区别:
-
二分查找:在某区间使用二分的思想进行查找
-
二分答案:在答案的区间中使用二分的思想并判断从而找到最优解
同时还要处理好二分的边界。
接下来来理解一下二分法的思想
每次都有一个左端点 \(l\) 和右端点 \(r\),然后判断这一段选中区间的中点 \(mid= \frac {(l+r)}{2}\) 是否满足条件,若满足则结束搜索;否则到这个中点的左侧/右侧寻找答案。因为二分每次查找的区间都是上一次的一半,所以最劣时间复杂度是 \(O(log_2(n))\) 的。
然后来看一下模版代码
先说明一下,\(x>>y\) 是位运算,意思是把 \(x\) 在二进制下右移 \(y\) 位,即 \(\lfloor \frac {x}{2^y} \rfloor\),左移 \(y\) 位则是 \(x<<y\),即 \(x \times 2^y\),这样会比直接使用 \(/\) 的效率更快,快读中的 \(ans=(ans<<3)+(ans<<1)+x\) 也是同样的道理。
- 使找到的答案尽可能靠左(即在一个升序排列中要求“最小的最大”)
python
while l<r:
mid=(l+r)>>1 #or (l+r)//2
if check(mid): #check 应为判断函数,并且应该返回一个布尔值
r=mid
else:
l=mid+1
c++
while(l<r){
int mid=(l+r)>>1; //or (l+r)/2
if(check(mid)) r=mid; //check 应为判断函数,并且应该返回一个布尔值
else l=mid+1;
}
- 使找到的答案尽可能靠右(即在一个升序排列中要求“最大的最小”)
python
while l<r:
mid=(l+r+1)>>1 #or (l+r+1)//2
if check(mid): #check 应为判断函数,并且应该返回一个布尔值
l=mid
else:
r=mid-1
c++
while(l<r){
int mid=(l+r+1)>>1; //or (l+r+1)/2
if(check(mid)) l=mid; //check 应为判断函数,并且应该返回一个布尔值
else r=mid-1;
}
接下来是二分答案
什么时候需要二分答案?
答案在一个很大的区间中,暴力会超时,这时就要使用二分答案了。
那怎么做呢?
首先要确定好初始范围,然后根据题意写一个 \(check\) 判断函数,最后看到底是“最小的最大”还是“最大的最小”从而套用模板。