C++로 크기를 알 수 없는 정렬된 배열에서 타겟 검색하기

오름차순으로 정렬된 배열이 주어졌을 때, 배열 안에서 특정 타겟 값을 찾는 함수를 정의해야 합니다. 타겟이 존재하면 해당 인덱스를 반환하고, 존재하지 않으면 -1을 반환합니다.

여기서 중요한 조건은 배열의 크기를 알 수 없다는 점입니다. 배열에 접근할 수 있는 유일한 방법은 ArrayReader 인터페이스를 사용하는 것으로, ArrayReader.get(k)를 호출하면 인덱스 k에 위치한 요소를 반환받을 수 있습니다.

예를 들어, 입력이 array = [-1,0,3,5,9,12], target = 9라면 출력은 4가 됩니다. 9가 배열에 존재하고 그 인덱스가 4이기 때문입니다.

해결 접근 방법

배열의 크기를 모르기 때문에 먼저 타겟 값이 포함될 만한 탐색 범위를 확정해야 합니다. 이를 위해 high 포인터를 두 배씩 지수적으로 증가시켜 상한을 찾고, 그 후 일반적인 이진 탐색으로 타겟을 찾습니다. 구체적인 단계는 다음과 같습니다.

high := 1, low := 0으로 초기화합니다.
reader.get(high)가 target보다 작은 동안 반복합니다.
- low := high로 갱신합니다.
- high를 두 배로 늘립니다(high = high * 2).
low <= high인 동안 이진 탐색을 수행합니다.
- mid := low + (high - low) / 2로 중간 인덱스를 계산합니다.
- x := reader.get(mid)로 중간값을 가져옵니다.
- x가 target과 같으면 mid를 반환합니다.
- x가 target보다 크면 high := mid - 1로 범위를 좁힙니다.
- 그렇지 않으면 low := mid + 1로 범위를 좁힙니다.
모든 탐색이 끝나도 찾지 못하면 -1을 반환합니다.

범위를 찾는 단계와 이진 탐색 단계 모두 O(log n)의 시간 복잡도를 가지므로, 전체 알고리즘의 시간 복잡도는 O(log n)입니다.

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

#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