배열이 처음에는 오름차순으로 증가하다가 어느 지점부터 내림차순으로 감소하는 특수한 구조를 가지고 있다고 가정해 봅시다. 이런 배열에서 최댓값을 효율적으로 찾는 것이 이번 글의 목표입니다.
예를 들어 배열이 A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1]과 같이 구성되어 있다면, 배열은 450까지 계속 증가한 후 다시 감소하기 시작합니다. 따라서 이 배열의 최댓값은 450입니다.
모든 요소를 하나씩 확인하는 선형 탐색으로도 해결할 수 있지만, 배열의 정렬된 성질을 활용하면 이진 탐색(Binary Search)을 통해 O(log n) 시간 복잡도로 훨씬 빠르게 최댓값을 찾을 수 있습니다.
이진 탐색 접근 방식
이진 탐색을 적용할 때는 중간(mid) 위치의 값과 인접한 두 요소를 비교하여 다음 세 가지 조건 중 하나에 해당하는지 판단합니다.
- mid 값이 양쪽 인접 요소보다 모두 클 때: mid가 곧 최댓값입니다.
- mid 값이 다음 요소보다는 크지만 이전 요소보다 작을 때: 최댓값은 mid의 왼쪽 영역에 있습니다.
- mid 값이 다음 요소보다는 작지만 이전 요소보다 클 때: 최댓값은 mid의 오른쪽 영역에 있습니다.
이 조건들을 재귀적으로 적용하면서 탐색 범위를 절반씩 줄여나가면 최종적으로 최댓값에 도달하게 됩니다.
C++ 구현 예제
#include<iostream>
using namespace std;
int getMaxElement(int array[], int left, int right) {
if (left == right)
return array[left];
if ((right == left + 1) && array[left] >= array[right])
return array[left];
if ((right == left + 1) && array[left] < array[right])
return array[right];
int mid = (left + right)/2;
if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])
return array[mid];
if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])
return getMaxElement(array, left, mid-1);
else
return getMaxElement(array, mid + 1, right);
}
int main() {
int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};
int n = sizeof(array)/sizeof(array[0]);
cout << "The maximum element is: " << getMaxElement(array, 0, n-1);
}실행 결과
The maximum element is: 450
코드 동작 원리
함수는 먼저 탐색 범위가 하나 또는 두 개의 요소로 좁혀졌을 때를 처리하는 기저 사례(base case)를 검사합니다. 그 후 탐색 범위의 중간 인덱스를 계산하고, 위에서 설명한 세 가지 조건에 따라 최댓값을 반환하거나 탐색 방향을 결정합니다.
이 알고리즘은 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에, n개의 요소를 가진 배열에서도 로그 시간 안에 답을 구할 수 있다는 점이 가장 큰 장점입니다. 대용량 데이터에서 선형 탐색(O(n))과 비교했을 때 성능 차이가 매우 크게 벌어집니다.