在C ++中搜索大小未知的排序数组

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数组，并且该数组按升序排序，我们必须定义一个函数以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

    以上是 在C ++中搜索大小未知的排序数组 的全部内容， 来源链接： utcz.com/z/340777.html

    回到顶部