[알고리즘] LeetCode - 33. Search in Rotated Sorted Array

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2].)
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm's runtime complexity must be in the order of O(logn).

번역) 오름차순으로 정렬된 배열이 특정 지점에서 회전되어 있다고 가정하자. 회전하는 축은 알려져있지 않다.(예를들어 배열 [0, 1, 2, 4, 5, 6, 7] 는 [4, 5, 6, 7, 0, 1, 2]가 된다.)
인풋으로 주어진 target값을 배열 내에서 찾아서 리턴하고 target값이 배열 내에 존재하지 않는다면 -1을 리턴하라.

• 배열 내에 중복되는 값은 없다고 가정한다.
• 알고리즘의 시간 복잡도는 O(logn)이어야 한다.

풀이

모든 배열을 순회하며 target값을 찾으면 간단하게 풀 수 있는 문제지만 logn의 시간복잡도로 문제를 해결하려면 이분탐색을 사용하여야 한다. 문제는 배열의 특정 부분이 rotate되어 있다는 점이다.

우선은 rotate된 지점을 찾아야 한다.

주어진 배열의 중간값을 선택하고 해당 값이 배열의 마지막 값보다 크다면 pivot 포인트는 오른쪽 부분 배열에 속함을 알 수 있다. 반대의 경우는 왼쪽 배열에서 찾으면 된다.

/**
 * @param {number[]} nums
 * @param {number} target
 */

let l = 0;
let r = nums.length - 1;

while (l < r) {
  const mid = Math.floor((l + r) / 2);
  if (nums[mid] > nums[r]) l = mid + 1;
  else r = mid;
}
// after while loop 'l' becomes pivot points index.

이렇게 찾은 pivot point를 저장해두고 다시 이진탐색을 시작한다.

const pivotPoint = l
l = 0;
r = nums.length - 1;

pivot point를 찾았으니 배열내의 요소들의 pivot이전의 실제 index를 알아낼 수 있다.

actualIndex = (index + pivotPoint) % nums.length;

작성 미완료