二分查找

函数 bsearch_l 寻找区间 $[l,r)$ 中 false -> true 的第一个 true。

函数 bsearch_r 寻找区间 $[l,r)$ 中 true -> false 的最后一个 true。

若无答案，返回 $r$。

i64 bsearch_l(i64 l, i64 r, auto check) {
	while (r - l > 1) {
		i64 m = l + (r - l) / 2;
		check(m - 1) ? r = m : l = m;
	}
	return check(l) ? l : r;
}

i64 bsearch_r(i64 l, i64 r, auto check) {
	while (r - l > 1) {
		i64 m = l + (r - l) / 2;
		check(m) ? l = m : r = m;
	}
	return check(l) ? l : r;
}

测试例题

• P1873 EKO / 砍树