C++로 정렬 후 회전된 배열에서 최댓값 찾기 – 이진 탐색 풀이

문제 설명

서로 다른 고유한 원소들로 구성된 정렬된 배열이 임의의 지점에서 회전된 상태로 주어졌을 때, 이 배열에서 최댓값을 찾는 문제입니다.

예를 들어 {30, 40, 50, 10, 20} 배열은 원래 {10, 20, 30, 40, 50} 순서로 정렬되어 있다가 특정 지점에서 회전한 형태입니다.

예시

입력 배열이 {30, 40, 50, 10, 20}이라면 최댓값은 50입니다.

알고리즘

• 최댓값은 '바로 다음 원소가 자신보다 작은' 유일한 원소입니다. 만약 그런 원소가 존재하지 않는다면 배열이 회전되지 않았다는 의미이며, 이 경우 마지막 원소가 곧 최댓값입니다.
• 중간(mid) 원소에 대해 이 조건을 검사합니다. 즉, arr[mid-1], arr[mid], arr[mid+1]을 서로 비교하여 해당 위치가 최댓값인지 판별합니다.
• 최댓값이 중간 위치(mid 또는 mid+1)에 없다면, 최댓값은 왼쪽 절반과 오른쪽 절반 중 한쪽에 반드시 존재합니다.
  • 중간 원소가 마지막 원소보다 크다면 → 최댓값은 왼쪽 절반에 있습니다.
  • 그렇지 않다면 → 최댓값은 오른쪽 절반에 있습니다.

이 방식은 매 단계마다 탐색 범위를 절반으로 줄여 나가므로 이진 탐색(binary search)과 동일한 원리로 동작합니다.

C++ 코드 구현

#include <bits/stdc++.h>
using namespace std;

int getMaxInSortedAndRotated(int arr[], int low, int high) {
    if (high < low) {
        return arr[0];
    }
    if (high == low) {
        return arr[high];
    }
    int mid = low + (high - low) / 2;
    if (mid < high && arr[mid + 1] < arr[mid]) {
        return arr[mid];
    }
    if (mid > low && arr[mid] < arr[mid - 1]) {
        return arr[mid - 1];
    }
    if (arr[low] > arr[mid]) {
        return getMaxInSortedAndRotated(arr, low, mid - 1);
    } else {
        return getMaxInSortedAndRotated(arr, mid + 1, high);
    }
}

int main() {
    int arr[] = {30, 40, 50, 10, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum element = " << getMaxInSortedAndRotated(arr, 0, n - 1) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Maximum element = 50

복잡도 분석

• 시간 복잡도: O(log n) — 매 재귀 호출마다 탐색 범위가 절반으로 줄어듭니다.
• 공간 복잡도: O(log n) — 재귀 호출 스택의 깊이에 비례합니다.