algorithm - 下界二进制搜索？

Question

如何在常规二分搜索中设置条件，以便找到最大值 x，使得 f(x) <= t 对于某个临界值 t？而不是意外返回最低的数字 > t。

现在我的界限是

if f(x) > t then high = x-1
else if f(x)< t then low = x+1
else return x

主要的 while 循环是 while low <= high

Answer 1

这个怎么样？

int ans = -1;

bsearch()
  if f(x) > t then high = x-1
  else if f(x)<= t then low = x+1, ans = x

另一种方法:

只需使用您当前的 bsearch 找到 f(x) 为最小值的 x > t，那么你想要的只是 x - 1 吗？ (如果存在)

PS:如果你使用的是C++，你可以使用upper_bound()找到x的位置，那么x-1就是你的答案