【C/C++】无限长有序数组中查找特定元素
在无限长有序数组中查找特定元素，由于数组长度未知，需先定位搜索范围，再进行二分查找。以下是C++实现：
#include <iostream>
#include <vector>
#include <climits>
using namespace std;// 假设数组访问函数，实际使用时需根据具体环境实现
// 示例中假设数组元素为int，若索引超出实际存储范围返回INT_MAX
int get(int index) {// 实际实现需替换为访问数组的逻辑// 这里仅为示例，假设数组在内存中足够大或通过其他方式访问static vector<int> arr = {1, 3, 5, 7, 9, 11, /* ... 无限有序元素 ... */};if (index < arr.size()) return arr[index];return INT_MAX; // 索引超界返回最大值（假设数组递增）
}int searchInfiniteArray(int target) {int low = 0;int high = 1;// 步骤1：指数扩展确定搜索范围while (get(high) < target) {low = high; // 移动下界high = high * 2; // 上界指数扩展}// 步骤2：标准二分查找while (low <= high) {int mid = low + (high - low) / 2;int midVal = get(mid);if (midVal == target) {return mid; // 找到目标} else if (midVal < target) {low = mid + 1;} else {high = mid - 1;}}return -1; // 未找到
}int main() {int target = 7;int index = searchInfiniteArray(target);if (index != -1) {cout << "元素 " << target << " 位于索引 " << index << endl;} else {cout << "元素 " << target << " 不存在" << endl;}return 0;
}
关键步骤解析：
-
动态确定搜索范围：
- 初始化
low = 0,high = 1 - 循环扩展：当
high处元素小于目标时，将low移至high，high倍增 - 终止条件：
high处元素 ≥ 目标或超界（返回INT_MAX）
- 初始化
-
二分查找：
- 在确定的
[low, high]区间内执行标准二分查找 - 通过
get(index)访问元素值 - 找到目标返回索引，否则返回
-1
- 在确定的
注意事项：
- 时间复杂度：
O(log T)，T为目标元素的索引位置 - 数组访问函数：需根据实际环境实现
get(index)，若索引超界应返回足够大的值（如INT_MAX） - 边界处理：当目标大于所有元素时，循环因超界终止，二分查找返回
-1 - 适用场景：适用于动态增长的有序数据流（如日志文件、实时数据流）
此方法高效利用指数扩展快速定位搜索范围，再通过二分查找精确匹配，适合处理无限或极大尺寸的有序数据集。