33. Search in Rotated Sorted Array

문제에서 O(logn)으로 풀어야 한다고 명시가 되어있다.

이 문제에서 중요한 부분은 두 배열로 나눴을 때 둘중 하나는 무조건 정렬된 상태라는 것이다. 그렇게 생각하면 왼쪽이 정렬되어있다면, 오른쪽은 정렬되지 않았을 것이고, 반대의 경우도 마찬가지이다. 왼쪽이 정렬된 상태일 경우에, 타겟이 그 정렬된 숫자들 사이에 있는 값이라면, right을 mid - 1 로 바꿔주고, 만약 타겟이 그 숫자들 사이에 있지 않다면, 그 left를 mid+1로 바꿔주면서 탐색한다.

 

const search = function(nums, target) {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid;
    }
    // 왼쪽 정렬 확인
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target <= nums[mid]) {
        // target is in the left
        right = mid - 1;
      } else {
        // target is in the right
        left = mid + 1;
      }
    } 

    // 오른쪽이 정렬
    else {
      if (nums[mid] <= target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }  
  }

  return -1;
};