C++でサイズが不明なソートされた配列を検索する

配列があり、昇順で並べ替えられているとすると、ターゲットをnumsで検索する関数を定義する必要があります。ターゲットが存在する場合はそのインデックスを返し、そうでない場合は-1を返します。

アレイのサイズは不明です。 ArrayReaderインターフェイスを使用してのみ配列にアクセスできます。 ArrayReader.get（k）のようなget関数があり、これはインデックスkにある配列の要素を返します。

したがって、入力がarray =[-1,0,3,5,9,12]、target =9の場合、9がnumsに存在し、そのインデックスが4であるため、出力は4になります。

これを解決するには、次の手順に従います-

• 高：=1、低：=0

• リーダーのget（high）

  • 低：=高

  • 高=高*2

• 低い<=高い間、実行-

  • 中：=低+（高-低）/ 2

  • x：=リーダーのget（mid）

  • xがターゲットと同じ場合、-

    • 途中で戻る

  • x>ターゲットの場合、-

    • 高：=中-1

  • それ以外の場合

    • 低：=中+ 1

• -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