二分搜技巧

1 minute read

上次團練的時候被學長建議了這種寫法，所以記錄一下。以往我都是寫

1
2
3
4
5

while (l < r) {
  int m = (l + r) >> 1;
  if (chk(m)) r = m;
  else l = m + 1; 
}

但有時候就會搞不清楚自己到底想要取什麼 = =，有點笨，所以換成下面的寫法

1
2
3
4
5

while (r - l > 1) {
  int m = (l + r) >> 1;
  if (chk(m)) l = m;
  else r = m;
}

這樣的寫法可以解釋成，如果 check mid 是對的，那麼我就提升左界，找到符合資格最大的，不然就下壓右界，然後因為停止條件是 $r - l == 1$，所以到時候 $l$ 就是合法的最大界，$r$ 會是不合法的最小界。