二分答案边界bug修正简论

Forgotten_0114507666 · 2024-09-07 21:08:59 · 算法·理论

本专栏专为解决我写二分答案题总是写成无限循环撰写。

为了方便，下文规定题目是（ll指的是long long）：

给定一个函数bool chk(ll x)，满足在 x\isin [l,m]时返回true，在 x\isin (m,r]时返回false，求 m。

我发现在发生无限循环时 l 和 r 往往差不了多少，那我在 r-l较小的时候（保证m\isin[l,r]）直接暴力把 m 找出来不就行了？

Code:

ll FgtFix(ll l,ll r);

//接下来是主程序
while(1){//r-l<=Fgt必定会在某时为真，此时循环就会结束
  if(r-l<=Fgt){m=FgtFix(l,r);break;}
  ll mid=(l+r)>>1;
  if(chk(mid))l=mid;
  else r=mid;
}

//FgtFix的具体实现
ll FgtFix(ll l,ll r){
  for(ll i=l;l<=r;i++)
    if(!chk(i))return --i;
  return r;
}

其中Fgt是一个整数常量，一般取 6。但如果你很自信，可以直接取 1。