黑盒 API 场景下如何做二分查找？如何减少调用次数？

简化版

黑盒 API 场景下，数组内容不能直接访问，只能通过接口判断某个位置或值。

这时仍然可以二分，但要把 API 调用看成主要成本。

做法是缓存已调用结果，避免同一个 mid 重复请求，并尽量把判断函数设计成单调谓词。

如果边界未知，还可以先倍增扩区间，再在区间内二分。

详细版

黑盒二分常见于题目给一个 guess(num)、isBadVersion(version)、reader.get(index) 之类的接口。

普通数组二分的访问成本是 O(1)，但黑盒接口可能很慢，甚至有调用次数限制。

所以面试中要强调 3 点：

先明确接口返回值和单调性
每次二分只调用必要接口
对重复调用做缓存

例如第一个坏版本：

function firstBadVersion(n, isBadVersion) {
  let left = 1
  let right = n
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (isBadVersion(mid)) right = mid
    else left = mid + 1
  }
  return left
}

这个判断单调：一旦某个版本坏了，后面的版本都坏。

完整版教学

1. 黑盒 API 二分考什么

黑盒题并不是考你会不会写普通二分，而是考你能不能在信息受限时仍然提炼单调性。

你不能直接看完整数组，只能问接口一个问题。

例如：

isBadVersion(x)：版本 x 是否坏
guess(x)：猜的数字偏大、偏小还是命中
reader.get(i)：返回第 i 个位置的值，越界时返回特殊值

黑盒二分的关键是把“接口回答”包装成一个可单调判断的谓词。

2. 调用次数是核心成本

普通二分复杂度写 O(log n) 就够了。

黑盒 API 场景下，还要说明 API 调用次数大约是 log n 次。

场景	普通成本	黑盒重点
数组访问	内存读，成本低	通常不用缓存
远程接口	网络或服务调用	减少请求次数
有调用限制	次数有限	避免重复 mid

如果一个分支里调用了两次相同接口，就应该保存结果。

3. 第一个坏版本

第一个坏版本是最典型的黑盒二分。

function firstBadVersion(n, isBadVersion) {
  let left = 1
  let right = n
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    const bad = isBadVersion(mid)
    if (bad) right = mid
    else left = mid + 1
  }
  return left
}

这里的谓词是 bad(x)。

如果 bad(mid) 为真，答案可能是 mid，所以保留 mid。

如果为假，答案只能在右边。

4. 猜数字问题

猜数字接口通常返回：

-1 表示猜大了
1 表示猜小了
0 表示猜中了

代码如下：

function guessNumber(n, guess) {
  let left = 1
  let right = n
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    const res = guess(mid)
    if (res === 0) return mid
    if (res < 0) right = mid - 1
    else left = mid + 1
  }
  return -1
}

这里不是找边界，而是根据接口给出的方向排除一半。

5. 边界未知时先倍增

有些黑盒数组没有告诉长度，只能 reader.get(index)。

可以先找右边界：

let left = 0
let right = 1
while (reader.get(right) < target) {
  left = right + 1
  right *= 2
}

然后在 [left, right] 内做二分。

这一步叫倍增扩区间，也叫指数搜索的一部分。

6. 常见面试追问

误区：把黑盒接口当普通数组随便访问。 如果接口很慢或有次数限制，重复调用会直接影响评分。
误区：没有确认接口返回语义。 guess 返回负数到底表示大了还是小了，必须先读清题。
误区：边界未知时直接二分。 没有右边界就没有搜索区间，应先倍增找范围。
追问：如何减少 API 调用？ 缓存同一个 mid 的结果，并保证每轮只做必要判断。
追问：如果接口结果不稳定怎么办？ 二分依赖稳定单调判断；接口不稳定时需要重试、投票或换算法，这已经超出标准二分假设。

这些点能体现你对真实工程成本的敏感度。

7. 复杂度分析

如果边界已知，调用次数是 O(log n)。

如果边界未知，倍增阶段是 O(log p)，二分阶段也是 O(log p)，其中 p 是目标位置附近的边界。

空间复杂度通常是 O(1)；如果做缓存，空间最多是调用过的 mid 数量，也就是 O(log n)。

8. 面试表达模板

可以这样回答：

“黑盒 API 场景下，我会先把接口返回转成单调判断，再做二分。因为接口调用可能昂贵，所以每轮只调用一次并保存结果。如果题目没有给长度，我会先倍增寻找包含目标的右边界，再在这个范围内二分。复杂度主要看接口调用次数，一般是对数级。”

简化版

详细版