二分查找

入门

回顾高中学过的知识，如果求一个单调递增或者单调递减的函数与x轴的交点，即 f(x)=0 时 x 的值， x∈[0,5]

image

我们知道 f(0)<0 , f(5)>0 ，那么， f(x) 与x轴的交点的横坐标一定落在区间 (0,5) 内，这时我们取x为0和5的中值，即2.5，发现 f(2.5)<0 ，那么 f(x) 与x轴的交点的横坐标一定落在区间 (2.5,5) 内，同理，我们取新的x为2.5和5的中值，发现 f(3.75)>0 ，那么 f(x) 与x轴的交点的横坐标一定落在区间 (2.5,3.75) 内......如此往复，我们得到的答案就会越来越逼近交点。

二分思想

这就是二分算法：通过不断检测左端点和右端点f(x)是否满足题意来减少未知数x的取值范围。这样最后肯定会不断逼近正确答案，直到最终左右端点非常靠近，端点值就是答案。

来一点数学语言

设计算x次能够得到答案，n是取值范围大小，即右端点-左端点。那么 2x =n,即经过x次二分可以得到n。 所以二分的时间复杂度是log(n)，计算机里log(n)就表示log(n)，所以时间复杂度是O(log(n))。

模板

普通二分

int l,r,res;
//l, r初始化,问题答案的左边界和右边界的确定
while(l<=r){
  int mid=(l+r)/2;
  if (ok(mid)){
      res=mid;
      r= mid-1;
  }
  else
      l=mid+1;    
}

浮点数二分模板

const double eps = 1e-7;
double l， r;
// l,r初始化，问题答案的左边界和右边界的确定
while (l + eps < r){
  double mid = (l + r) / 2.0;
  if (ok (mid)){
      l = mid;
      // r = mid;   
  }
  else {
      r = mid;
      // l = mid;
  }
}