C++로 정렬된 0과 1 배열에서 전환점(첫 번째 '1'의 위치) 찾기

0과 1만으로 이루어진 정렬된 배열이 주어졌을 때, 전환점(Transition Point)을 찾는 문제입니다. 여기서 전환점이란 배열에서 처음으로 '1'이 등장하는 인덱스를 의미합니다.

다음 예시를 통해 살펴보겠습니다.

입력-1 −

N = 6
arr[ ] = {0,0,0,0,1,1}

출력 −

설명 − 주어진 배열에서 처음 '1'이 나타나는 위치는 인덱스 '4'이므로, 결과값은 4가 됩니다.

입력-2 −

N = 5
arr[ ] = {0,0,1,1,1}

출력 −

설명 − 위 배열에서 처음 '1'이 등장하는 인덱스는 '2'이므로, 결과값으로 2를 반환합니다.

문제 해결 접근 방법

주어진 정수 배열에서 첫 번째 '1'의 인덱스를 찾아야 합니다. 배열이 이미 정렬되어 있다는 점을 활용하면, 이진 탐색(Binary Search) 알고리즘으로 문제를 효율적으로 해결할 수 있습니다. 선형 탐색(O(N))보다 이진 탐색(O(log N))이 훨씬 빠른 성능을 보여줍니다.

N개의 0과 1로 구성된 배열을 입력받습니다.
transitionPoint(int *arr, int n) 함수는 배열과 그 크기를 입력으로 받아, 배열에서 처음 등장하는 '1'의 인덱스를 반환합니다.
두 개의 포인터 low와 high를 각각 '0'과 'n-1'로 초기화합니다.
배열의 중간 지점(mid)을 계산한 뒤, 해당 위치의 값이 '1'인지 확인합니다.
중간 값이 '1'이라면 바로 그 앞 요소까지 확인합니다. 앞 요소가 '0'이거나 mid가 0이라면 현재 인덱스가 전환점이므로 해당 값을 반환하고, 그렇지 않으면 탐색 범위를 왼쪽 절반으로 줄입니다.
중간 값이 '0'이라면 low 포인터를 mid+1로 이동시켜 오른쪽 절반에서 계속 탐색합니다.
'1'을 찾거나 탐색 범위가 끝날 때까지 위 과정을 반복합니다.

만약 배열에 '1'이 하나도 없다면 -1을 반환하도록 처리합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
int transitionPoint(int *arr, int n){
    int low=0;
    int high= n-1;
    while(low<=high){
        int mid = (low+high)/2;
        if(arr[mid]==0)
            low= mid+1;
        else if(arr[mid]==1){
            if(mid==0 || (mid>0 && arr[mid-1]==0))
                return mid;
            high= mid-1;
        }
    }
    return -1;
}
int main(){
    int n= 6;
    int arr[n]= {0,0,0,1,1,1};
    int ans= transitionPoint(arr,n);
    if(ans>=0){
        cout<<"Transition Point is:"<<ans<<endl;
    }
    else{
        cout<<"Not Found"<<endl;
    }
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Transition Point is: 3

주어진 배열 {0,0,0,1,1,1}에서 처음 '1'이 나타나는 위치는 인덱스 '3'이므로, 실행 결과로 '3'이 출력됩니다. 이 알고리즘은 매 단계마다 탐색 범위를 절반으로 줄여 나가기 때문에 시간 복잡도는 O(log N), 공간 복잡도는 O(1)로 매우 효율적입니다.