C++로 0과 1의 무한 정렬 배열에서 첫 번째 1의 인덱스 찾는 방법

문제 개요

이 문제에서는 0과 1(boolean 값)만으로 구성되어 있고 오름차순으로 정렬된 무한 배열 bin[]이 주어집니다. 우리가 해야 할 일은 이 무한 배열에서 처음 등장하는 1의 인덱스를 찾는 것입니다.

배열은 무한하다고 가정하지만, 반드시 배열 안에 1이 존재한다는 것이 보장됩니다.

문제 이해를 위한 예시

입력 : bin[] = {0, 0, 0, 1, 1, ....}
출력 : 3

설명 −

배열에서 처음 1이 나타나는 위치는 인덱스 3입니다.

해결 접근 방법

핵심은 배열에서 가장 먼저 나오는 1의 위치를 찾는 것이므로, 다양한 탐색 기법을 활용할 수 있습니다.

방법 1 : 선형 탐색 (Linear Search)

가장 직관적인 방법입니다. 배열을 처음부터 순서대로 순회하며 값이 1인 원소를 만나면 해당 인덱스를 반환합니다. 무한 루프를 사용해 순회하고, 1을 찾지 못할 경우 -1을 출력하도록 처리합니다.

다음은 이 방식의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;

double find1stOneInfiniteArray(int bin[]) {
   int i = 0;
   while(1){
      if (bin[i] == 1)
         return i;
      i++;
   }
   return -1;
}

int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1 };
   cout<<"무한 배열에서 첫 번째 1의 인덱스는 "<<find1stOneInfiniteArray(bin);
   return 0;
}

출력 결과

무한 배열에서 첫 번째 1의 인덱스는 3

방법 2 : 이진 탐색 (Binary Search)

배열이 이미 정렬되어 있으므로 더 효율적인 이진 탐색을 적용할 수 있습니다.

일반적인 이진 탐색과 달리 이 문제에서는 상한(high)이 정해져 있지 않습니다. 따라서 high 값을 인덱스 1부터 시작해 두 배씩 늘려가면서, 처음으로 1이 등장하는 구간의 범위(low ~ high)를 찾아냅니다.

이렇게 확보한 경계값을 이용해 이진 탐색을 수행하면 첫 번째 1의 인덱스를 효율적으로 구할 수 있습니다. 시간 복잡도는 O(log n)으로 선형 탐색보다 훨씬 빠릅니다.

다음은 이 방식의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;

double find1stOneInfiniteArray(int bin[], int low, int high) {
   int mid;
   while (low <= high) {
      mid = (low + high) / 2;
      if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
         return mid;
      else if (bin[mid] == 1)
         high = mid - 1;
      else
         low = mid + 1;
   }
   return -1;
}

int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
   int low = 0;
   int high = 1;
   while(bin[high] != 1){
      low = high;
      high *= 2;
   }
   cout<<"무한 배열에서 첫 번째 1의 인덱스는 " <<find1stOneInfiniteArray(bin,low, high);
   return 0;
}

출력 결과

무한 배열에서 첫 번째 1의 인덱스는 3

정리

정렬된 무한 배열에서 첫 번째 1을 찾는 문제는 단순 선형 탐색으로도 해결 가능하지만, 상한을 지수적으로(두 배씩) 확장한 후 이진 탐색을 결합하면 O(log n)의 효율성을 얻을 수 있습니다. 이는 정렬된 데이터에서 특정 조건을 만족하는 첫 번째 위치를 찾는 전형적인 패턴으로, 실전 알고리즘 문제에서 자주 응용됩니다.