C语言指数搜索算法详解（高效查找有序数组的利器）

为什么叫“指数”搜索？

因为算法在初始阶段以 1, 2, 4, 8, 16...（即 2⁰, 2¹, 2², 2³, 2⁴...）这样的指数方式跳跃，快速扩大搜索范围，因此得名“指数搜索”。

算法步骤详解

1. 边界检查：如果数组为空或第一个元素就是目标值，直接返回。
2. 指数跳跃：从索引 1 开始，每次将索引乘以 2（即 1 → 2 → 4 → 8...），直到找到一个位置 i，使得 arr[i] > target 或 i 超出数组边界。
3. 确定区间：目标值一定在 [i/2, min(i, n-1)] 这个区间内。
4. 二分查找：在上述区间内执行标准的二分查找。

C语言实现代码

下面是一个完整的 C 语言实现，包含二分查找辅助函数和主指数搜索函数：

// 二分查找辅助函数int binarySearch(int arr[], int left, int right, int x) {    while (left <= right) {        int mid = left + (right - left) / 2;        if (arr[mid] == x)            return mid;        if (arr[mid] < x)            left = mid + 1;        else            right = mid - 1;    }    return -1; // 未找到}// 指数搜索主函数int exponentialSearch(int arr[], int n, int x) {    // 如果第一个元素就是要找的    if (arr[0] == x)        return 0;    // 指数跳跃：找到范围 [bound/2, min(bound, n-1)]    int bound = 1;    while (bound < n && arr[bound] <= x) {        bound *= 2;    }    // 在 [bound/2, min(bound, n-1)] 区间内二分查找    return binarySearch(arr, bound / 2,                          (bound < n) ? bound : n - 1, x);}

使用示例

#include <stdio.h>int main() {    int arr[] = {2, 3, 4, 10, 40, 50, 60, 70, 80, 90};    int n = sizeof(arr) / sizeof(arr[0]);    int x = 10;    int result = exponentialSearch(arr, n, x);    if (result == -1)        printf("元素未找到\n");    else        printf("元素 %d 位于索引 %d\n", x, result);    return 0;}

时间复杂度分析

- 最坏情况：O(log i)，其中 i 是目标元素的索引。
- 最好情况：O(1)，当目标是第一个元素时。
- 平均情况：优于线性搜索，接近二分查找效率。

相比普通二分查找（O(log n)），指数搜索在目标靠近数组开头时更快，尤其适合无限长或动态增长的有序序列。

适用场景

• 数组非常大，甚至长度未知（如流数据）
• 目标元素大概率出现在数组前半部分
• 需要比线性搜索更快、又不想每次都对整个数组做二分查找的场景

总结

通过本教程，你已经掌握了 C语言指数搜索算法 的原理与实现。它结合了指数跳跃和二分查找的优势，是一种高效的指数查找方法。无论你是学习C语言查找算法的新手，还是想优化现有程序的开发者，这种高效搜索算法都值得你加入工具箱！

动手试试吧！修改代码中的数组和目标值，观察输出结果，加深理解。