在C ++中搜索大小未知的排序数组
假设我们有一个数组，并且该数组按升序排序，我们必须定义一个函数以nums搜索目标。如果存在目标，则返回其索引，否则返回-1。
数组大小未知。我们只能使用ArrayReader接口访问该数组。有一个类似ArrayReader.get(k)的get函数，它将返回索引k处的数组元素。
因此，如果输入类似于array=[-1,0,3,5,9,12]，target=9，则输出将为4，因为存在9个数字，其索引为4
为了解决这个问题，我们将遵循以下步骤-
高：=1，低：=0
当阅读器的get(high)<目标时，执行-
低：=高
高=高*2
当低<=高时，执行-
低：=中+1
高：=中-1
返回中
中：=低+（高-低）/2
x：=阅读器的get(mid)
如果x与目标相同，则-
如果x>目标，则-
除此以外
返回-1
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class ArrayReader{
private:
vector<int> v;
public:
ArrayReader(vector<int> &v){
this->v = v;
}
int get(int i){
return v[i];
}
};
class Solution {
public:
int search(ArrayReader& reader, int target) {
int high = 1;
int low = 0;
while (reader.get(high) < target) {
low = high;
high <<= 1;
}
while (low <= high) {
int mid = low + (high - low) / 2;
int x = reader.get(mid);
if (x == target)
return mid;
if (x > target) {
high = mid - 1;
}
else
low = mid + 1;
}
return -1;
}
};
main(){
Solution ob;
vector<int> v = {-1,0,3,5,9,12};
ArrayReader reader(v);
cout<<(ob.search(reader, 9));
}输入值
{-1,0,3,5,9,12}, 9输出结果
4