자바스크립트로 회전된 정렬 배열에서 최솟값 찾는 방법 (이진 탐색 활용)

문제 개요

정수 배열을 유일한 인수로 받아 처리하는 자바스크립트 함수를 작성해야 합니다.

이 배열은 처음에 오름차순으로 정렬된 상태였다가, 임의의 횟수만큼 회전(rotate)된 형태입니다. 우리가 만들 함수는 이 배열에서 가장 작은 요소를 찾아 반환해야 합니다.

여기서 중요한 조건은 선형 시간 복잡도(O(n))보다 빠른 속도, 즉 O(log n) 시간 안에 문제를 해결해야 한다는 점입니다. 이를 위해서는 기본적인 이진 탐색(Binary Search) 알고리즘을 약간 변형하여 사용하는 것이 효과적입니다.

예시

입력 배열이 다음과 같다면 −

const arr = [6, 8, 12, 25, 2, 4, 5];

이 배열은 [2, 4, 5, 6, 8, 12, 25]에서 뒤쪽 일부가 앞으로 회전된 형태이므로, 가장 작은 요소인 2가 출력되어야 합니다.

접근 방식: 변형된 이진 탐색

회전된 정렬 배열의 핵심 특징은 배열이 두 개의 정렬된 구간으로 나뉘어 있다는 점입니다. 따라서 매 단계마다 중간값과 경계값을 비교하면 최솟값이 어느 쪽 절반에 위치하는지 판단할 수 있고, 탐색 범위를 절반씩 줄여나갈 수 있습니다.

구현 코드

const arr = [6, 8, 12, 25, 2, 4, 5];
const findMin = (arr = []) => {
   let temp;
   let min = 0;
   let max = arr.length - 1;
   let currentMin = Number.POSITIVE_INFINITY;
   while (min <= max) {
      temp = (min + max) >> 1;
      currentMin = Math.min(currentMin, arr[temp]);
      if (arr[min] < arr[temp] && arr[temp] <= arr[max] || arr[min] > arr[temp]) {
         max = temp - 1;
      } else if (arr[temp] === arr[min] && arr[min] === arr[max]) {
         let guessNum = arr[temp];
         while (min <= max && arr[min] === guessNum) {
            min++;
         }
      } else {
         min = temp + 1;
      }
   }
   return currentMin;
};
console.log(findMin(arr));

코드 동작 원리

포인터 초기화: 탐색 범위의 양 끝을 가리키는 min(0)과 max(배열 길이 - 1)를 설정하고, 최솟값 후보 currentMin은 무한대로 초기화합니다.
중간값 확인: 비트 연산자 >>를 사용해 중간 인덱스 temp를 구하고, 해당 위치의 값으로 현재 최솟값을 갱신합니다.
왼쪽 탐색 조건: 구간 전체가 정렬되어 있거나(arr[min] < arr[temp]이면서 arr[temp] <= arr[max]), arr[min] > arr[temp]로 회전 지점이 왼쪽 절반에 있다면 max = temp - 1로 탐색 범위를 왼쪽으로 좁힙니다.
중복 요소 처리: 세 지점의 값이 모두 같은 경우 최솟값의 위치를 판단할 수 없으므로, min을 한 칸씩 이동하며 중복을 제거합니다.
오른쪽 탐색: 위 조건에 해당하지 않으면 최솟값은 오른쪽 절반에 있으므로 min = temp + 1로 탐색 범위를 이동합니다.

이 방식은 서로 다른 값으로 이루어진 배열에서 평균적으로 O(log n)의 시간 복잡도로 동작하며, 중복 요소가 많은 최악의 경우에도 정확한 결과를 보장합니다.

실행 결과

콘솔 출력은 다음과 같습니다 −