在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