跳数查找先通过倍增索引快速定位目标区间，再在该区间内执行二分查找，适用于有序且长度未知的大数组，时间复杂度为O(log i)，当目标靠近起始位置时效率优于传统二分查找。
跳数查找（Galloping Search），也叫指数搜索（Exponential Search），是一种结合了跳跃式探测和二分查找的高效算法，适用于有序但长度未知或非常大的数组中查找目标值。它在某些场景下比纯二分查找更高效，尤其是当目标元素靠近数组起始位置时。
基本思路：先“跳”，再“找”
跳数查找的核心思想是：
从索引1开始，不断翻倍跳跃（1, 2, 4, 8, …），直到找到一个位置，使得该位置的值大于等于目标值。此时确定了一个范围 [prev_index, current_index]，在这个范围内使用二分查找精确定位目标。
这种方法避免了对整个数组进行扫描，也不需要事先知道数组的确切长度。
C++ 实现代码
以下是一个完整的 C++ 实现，支持整型数组中的跳数查找：
立即学习“C++免费学习笔记（深入）”；
#include #include #include using namespace std;// 二分查找辅助函数int binarySearch(const vector& arr, int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;else if (arr[mid] < target)left = mid + 1;elseright = mid - 1;}return -1; // 未找到}
// 跳数查找主函数int gallopingSearch(const vector& arr, int target) {int n = arr.size();if (n == 0) return -1;
// 如果第一个元素就是目标if (arr[0] == target) return 0;// 跳跃阶段：找到一个区间 [bound/2, min(bound, n-1)]int bound = 1;while (bound < n && arr[bound] < target) { bound *= 2;}// 现在在 [bound/2, min(bound, n-1)] 内做二分查找int left = bound / 2;int right = min(bound, n - 1);return binarySearch(arr, left, right, target);
}
使用示例与测试
下面是一个简单的测试用例：
int main() { vector arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}; int target = 9;int result = gallopingSearch(arr, target);if (result != -1) cout << "元素 " << target << " 在索引 " << result << " 处找到。n";else cout << "元素 " << target << " 未找到。n";return 0;
}
时间复杂度分析
跳数查找的时间复杂度为 O(log i)，其中 i 是目标元素在数组中的索引位置。
跳跃阶段最多进行 log(i) 次比较。二分查找阶段在大小约为 i 的区间内进行，耗时 O(log i)。
相比标准二分查找的 O(log n)，当目标靠前时（i
基本上就这些。跳数查找适合用于稀疏查找、流式数据或无界有序序列的场景，C++ 中通过 vector 结合指数增长和 lower_bound 扩展也能实现变体。关键是理解“先快跳，后细查”的逻辑。不复杂但容易忽略边界处理。
以上就是C++怎么实现一个跳数查找(Galloping Search)_C++结合指数搜索与二分查找的高效算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486684.html
微信扫一扫 
支付宝扫一扫 
