C++에서 알 수 없는 크기의 정렬된 배열에서 검색

<시간/>

배열이 있고 오름차순으로 정렬되어 있다고 가정하면 대상을 숫자로 검색하는 함수를 정의해야 합니다. 대상이 있으면 해당 인덱스를 반환하고, 그렇지 않으면 -1을 반환합니다.

배열 크기를 알 수 없습니다. ArrayReader 인터페이스를 사용해서만 배열에 액세스할 수 있습니다. ArrayReader.get(k)와 같은 get 함수가 있습니다. 이것은 인덱스 k에 있는 배열의 요소를 반환합니다.

따라서 입력이 array =[-1,0,3,5,9,12], target =9와 같으면 9가 숫자로 존재하고 인덱스가 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