什么是指数搜索？不知道数组长度或边界时如何先扩区间再二分？

简化版

指数搜索适合不知道右边界，或者数据结构只能按下标访问但长度未知的场景。

它先从 1 开始不断把右边界翻倍：1, 2, 4, 8...，直到找到一个可能包含答案的区间，再在这个区间里做普通二分。

核心思路是先用指数级扩张快速圈住答案，再用二分精确定位。

详细版

如果目标值在有序数组中的位置是 pos，指数扩张最多做 O(log pos) 次就能找到一个右边界。

例如查找 target：

hi = 1
while value(hi) < target:
  hi *= 2

然后答案如果存在，一定在：

(hi / 2, hi]

再对这个区间二分。

阶段	作用	复杂度
指数扩张	找到包含答案的范围	`O(log pos)`
二分查找	精确定位答案	`O(log pos)`

它常用于无限有序数组、流式索引、黑盒 get(i) 访问等题。

完整版教学

1. 普通二分为什么需要边界

普通二分查找必须知道搜索区间。

常见写法是：

lo = 0
hi = n - 1

如果题目不给数组长度，或者不能直接拿到右边界，就没法直接二分。

这时需要先找一个足够大的 hi。

2. 指数扩张怎么找右边界

指数搜索用倍增方式扩张。

hi = 1
while get(hi) < target:
  hi = hi * 2

假设第一次满足 get(hi) >= target，而上一次位置是 hi / 2。

那么目标如果存在，就在：

[hi / 2 + 1, hi]

或者加上边界后写成 [lo, hi]。

指数搜索的美感在于：不知道边界没关系，先用倍增快速制造一个边界。

3. 为什么不是一个个往后找

线性扩张是：

1, 2, 3, 4, 5...

如果答案在第 1,000,000 个位置，线性扩张要走很多步。

指数扩张是：

1, 2, 4, 8, 16...

只需要大约 log2(1,000,000) 次就能超过答案位置。

4. 找到区间后如何二分

找到右边界后，普通二分即可。

lo = hi / 2 + 1
while lo <= hi:
  mid = lo + (hi - lo) / 2
  if get(mid) == target: return mid
  if get(mid) < target: lo = mid + 1
  else: hi = mid - 1

如果 hi / 2 位置也可能是答案，可以根据初始化写成 [hi/2, hi]，关键是区间不要漏。

5. get 越界怎么办

黑盒数组可能访问越界。

常见处理方式：

场景	处理
`get(i)` 越界返回无穷大	直接把它当成右边界
`get(i)` 抛异常	捕获后缩小或认为右边界足够
API 返回特殊值	按大于 target 处理

面试中要主动说明越界语义，否则代码不完整。

6. 和 lower_bound 的关系

指数搜索只是解决右边界未知的问题。

真正查找时，可以找等于目标，也可以找第一个大于等于目标的位置。

first index where get(i) >= target

这时后半段本质就是 lower_bound。

7. 复杂度怎么分析

如果答案位置是 pos，扩张阶段需要：

O(log pos)

二分阶段区间长度也在 pos 同阶，所以也是：

O(log pos)

总复杂度仍是 O(log pos)，空间 O(1)。

8. 常见误区与追问

误区：不知道长度就不能二分。 可以先用指数扩张找出包含答案的区间。
误区：扩张应该每次加 1。 倍增才能保持对数级边界发现速度。
误区：找到 hi 后答案一定存在。 只能说明答案如果存在会在区间内，仍要二分验证。
追问：如果 get 越界怎么办？ 根据 API 语义处理，常见是把越界视为正无穷或捕获异常。
追问：复杂度为什么是 O(log pos)？ 因为右边界按 2 倍增长，超过位置 pos 只需对数次。

简化版

详细版