指数查找
入门适合未知边界或前部更可能命中的有序数据。
// 搜索输入
定义数组和目标值
可视化演示开发中
指数查找 的交互式动画即将上线，敬请期待。
1int exponentialSearch(int arr[], int n, int target) {
2 if (arr[0] == target) return 0;
3 int bound = 1;
4 while (bound < n && arr[bound] < target) {
5 bound *= 2;
6 }
7 int left = bound / 2;
8 int right = min(bound, n - 1);
9 while (left <= right) {
10 int mid = left + (right - left) / 2;
11 if (arr[mid] == target) return mid;
12 if (arr[mid] < target) left = mid + 1;
13 else right = mid - 1;
14 }
15 return -1;
16}
复杂度分析
时间 O(log n)
空间 O(1)
最优 O(1)
最坏 O(log n)
算法讲解
指数查找的第一阶段不是直接对半，而是按 1、2、4、8 这样的节奏快速扩张右边界。
这种扩张方式特别适合"数组很大，但目标可能靠前"或"有效范围未知"的查找场景。
当边界第一次覆盖目标后，算法就能把问题转换成一个更小区间上的二分查找。
因此动画会明显分成两个阶段：先看边界翻倍扩张，再看区间内的二分收缩。
它本质上是把"快速逼近目标区域"和"稳定定位目标位置"这两件事组合在一起。
时间复杂度为 O(log n)，空间复杂度为 O(1)。