C++ 이진 탐색으로 등차수열에서 누락된 숫자 찾기

문제 개요

배열이 등차수열의 요소들을 순서대로 담고 있고, 그중 한 개의 요소가 누락되어 있다고 가정해 보겠습니다. 이때 우리가 해야 할 일은 바로 그 누락된 요소를 찾아내는 것입니다.
예를 들어 arr = [2, 4, 8, 10, 12, 14]라면 공차가 2인 등차수열에서 6이 빠져 있으므로, 정답은 6이 됩니다.

접근 방법: 이진 탐색 활용

요소를 하나씩 순회하는 선형 탐색 대신 이진 탐색(Binary Search)을 활용하면 O(log n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다. 알고리즘의 핵심 로직은 다음과 같습니다.

먼저 배열의 중간 요소(mid)를 확인한 뒤, 중간 요소와 그 다음 요소 사이의 차이가 실제 공차(diff)와 같은지 검사합니다. 차이가 다르다면 누락된 요소는 mid와 mid + 1 인덱스 사이에 존재하는 것이므로 바로 값을 구할 수 있습니다.
만약 중간 요소가 등차수열 전체 기준 n/2번째 위치에 정확히 해당한다면(즉, arr[mid] == arr[0] + mid * diff), 누락된 요소는 오른쪽 절반에 있는 것이고, 그렇지 않다면 왼쪽 절반에 있는 것입니다. 이 과정을 범위를 좁혀 가며 반복합니다.

예제 코드

#include <iostream>
using namespace std;
class Progression {
    public:
    int missingUtil(int arr[], int left, int right, int diff) {
        if (right <= left)
            return INT_MAX;
        int mid = left + (right - left) / 2;
        if (arr[mid + 1] - arr[mid] != diff)
            return (arr[mid] + diff);
        if (mid > 0 && arr[mid] - arr[mid - 1] != diff)
            return (arr[mid - 1] + diff);
        if (arr[mid] == arr[0] + mid * diff)
            return missingUtil(arr, mid + 1, right, diff);
        return missingUtil(arr, left, mid - 1, diff);
    }
    int missingElement(int arr[], int n) {
        int diff = (arr[n - 1] - arr[0]) / n;
        return missingUtil(arr, 0, n - 1, diff);
    }
};
int main() {
    Progression pg;
    int arr[] = {2, 4, 8, 10, 12, 14};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The missing element is: " << pg.missingElement(arr, n);
}

실행 결과

The missing element is: 6

동작 원리 정리

위 코드에서 공차는 (마지막 값 - 첫 번째 값) / n으로 계산됩니다. 요소가 하나 빠져 있기 때문에 전체 길이 n으로 나누면 실제 공차가 정확하게 도출됩니다. 이후 재귀 호출을 통해 탐색 범위를 절반씩 줄여 나가므로, 배열 크기가 커져도 성능 저하 없이 누락된 숫자를 빠르게 찾을 수 있습니다.