LeetCode No.33

카테고리: Algorithms

January 05, 2022

문제링크

접근

우선 이진 탐색을 활용하여 피벗을 찾습니다. 이렇게 찾은 피벗을 기준으로 나뉜 두 배열은 각자 정렬된 상태이므로 이 두 배열에 대해 이진 탐색을 수행하여 최종 결과값을 도출하고자 하였습니다.

피벗을 찾는 아이디어는 다음과 같습니다:

Finding pivot overview — 배열이 피벗을 기준으로 나뉜 모습

위 그림과 같이, 오름차순으로 정렬된 배열이 피벗을 기준으로 둘로 나뉜 상황에서, 아래의 그림처럼 lo와 hi 그리고 mid를 통해 피벗을 찾아나갈 수 있습니다:

이 상황에서 잘 생각해보면, mid 요소의 값과 lo, hi 요소의 값을 서로 비교하여 피벗의 인덱스를 알아낼 수 있습니다.

위 그래프에 있는 배열을 나타내는 두 직선에 대해, 만약 mid 요소의 값이 hi 요소의 값보다 크다면, lo와 mid가 같은 직선(즉, 배열) 에 존재함을 알 수 있습니다. 이 경우 mid를 포함하여 mid보다 왼쪽에 있는 요소에는 피벗이 존재하지 않음을 알 수 있으므로, lo값을 mid + 1로 옮겨서 피벗을 계속 찾아나가야 합니다.

반대의 경우도 마찬가지입니다. 만약 mid 요소의 값이 hi 요소의 값보다 작다면, hi와 mid가 같은 직선(배열)에 존재함을 알 수 있습니다. 하지만 이 경우엔 hi의 값을 mid - 1이 아니라 mid로 조정해야 합니다. 왜냐면 mid가 피벗이 될 수도 있기 때문이죠.

Finding pivot when mid is greater than hi

이런식으로 lo와 hi를 좁혀나가면서, lo === hi가 되는 경우 해당 위치가 피벗임을 알 수 있습니다:

이제 이렇게 찾은 피벗을 기준으로, 각각의 두 배열에 대해 따로 이진 탐색을 수행하면 O(log n) 시간에 우리가 원하는 답을 얻을 수 있게 됩니다.

자바스크립트 구현

function search(nums, target) { 
  const pivot = findPivot(nums);
  const leftResult = binarySearch(nums, target, 0, pivot - 1);
  const rightResult = binarySearch(nums, target, pivot, nums.length - 1);
  
  if (leftResult === -1 && rightResult === -1) return -1;
  return leftResult !== -1 ? leftResult : rightResult;
}

function findPivot(nums) {
  let lo = 0;
  let hi = nums.length - 1;
  
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    
    if (nums[mid] < nums[hi]) hi = mid;
    else lo = mid + 1;
  }
  
  return lo;
}

function binarySearch(nums, target, lo, hi) {
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  
  return -1;
}