C++怎么实现一个跳数查找(Galloping Search)_C++结合指数搜索与二分查找的高效算法

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++怎么实现一个跳数查找(Galloping Search)_C++结合指数搜索与二分查找的高效算法

2025-11-28

浏览次数：次

返回列表

跳数查找先通过倍增索引快速定位目标区间，再在该区间内执行二分查找，适用于有序且长度未知的大数组，时间复杂度为O(log i)，当目标靠近起始位置时效率优于传统二分查找。

c++怎么实现一个跳数查找(galloping search)_c++结合指数搜索与二分查找的高效算法

跳数查找（Galloping Search），也叫指数搜索（Exponential Search），是一种结合了跳跃式探测和二分查找的高效算法，适用于有序但长度未知或非常大的数组中查找目标值。它在某些场景下比纯二分查找更高效，尤其是当目标元素靠近数组起始位置时。

基本思路：先“跳”，再“找”

跳数查找的核心思想是：

从索引1开始，不断翻倍跳跃（1, 2, 4, 8, ...），直到找到一个位置，使得该位置的值大于等于目标值。
此时确定了一个范围 [prev_index, current_index]，在这个范围内使用二分查找精确定位目标。

这种方法避免了对整个数组进行扫描，也不需要事先知道数组的确切长度。

C++ 实现代码

以下是一个完整的 C++ 实现，支持整型数组中的跳数查找：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>// 二分查找辅助函数
int binarySearch(const vector<int>& 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;
else
right = mid - 1;
}
return -1; // 未找到
}</p><p>// 跳数查找主函数
int gallopingSearch(const vector<int>& arr, int target) {
int n = arr.size();
if (n == 0) return -1;</p><pre class='brush:php;toolbar:false;'>// 如果第一个元素就是目标
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);

}

使用示例与测试

下面是一个简单的测试用例：

N世界

一分钟搭建会展元宇宙

138 查看详情 N世界

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};
    int target = 9;
<pre class='brush:php;toolbar:false;'>int result = gallopingSearch(arr, target);
if (result != -1)
    cout << "元素 " << target << " 在索引 " << result << " 处找到。\n";
else
    cout << "元素 " << target << " 未找到。\n";

return 0;