[LeetCode] Search in Rotated Sorted Array - Javascript

Search in Rotated Sorted Array

[특정 값을 기준으로 뒤바뀌어 정렬이 되어 있는 배열의 target 찾기]

제약 조건 

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10^4 <= target <= 10^4

 

Example

ex1) Input: nums = [4,5,6,7,0,1,2], target = 0
     Output: 4

ex2) Input: nums = [4,5,6,7,0,1,2], target = 3
     Output: -1

ex3) Input: nums = [1], target = 0
     Output: -1

문제 접근 방식

You must write an algorithm with O(log n) runtime complexity.

해당 문제는 O(log n)으로 풀이 해야 하기에 이진 탐색이 필요하다고 생각했다.

 

num[start]가 nums[mid]보다 작다면 start부터 mid까지의 정렬이 정상적으로 되어있다는 의미이다.
ex) [4,5,6,7,0,1,2]
정렬이 제대로 되어 있는 상태에서 nums[start]가 target보다 작고 target이 nums[mid]보다 작으면
target과 mid 사이의 결괏값이 있을 거라고 추측이 가능하다는 의미이기에 end를 mid-1로 업데이트한다.
(배열의 절반 중 왼쪽을 선택한다는 의미.)
아니라면 오른쪽을 선택한다는 의미로 start를 mid+1로 초기화한다.

       if (nums[start] <= nums[mid]) {
           if (nums[start] <= target && target < nums[mid]) {
               end = mid - 1;
           } else {
               start = mid + 1;
           }
       } else {
           if (nums[mid] < target && target <= nums[end]) {
               start = mid + 1;
           } else {
               end = mid - 1;
           }
       }

sovle 코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
   let start = 0, end = nums.length - 1;

   while (start <= end) {
       let mid = Math.floor((start + end) / 2);

       if (nums[mid] === target) {
           return mid;
       }

       if (nums[start] <= nums[mid]) {
           if (nums[start] <= target && target < nums[mid]) {
               end = mid - 1;
           } else {
               start = mid + 1;
           }
       } else {
           if (nums[mid] < target && target <= nums[end]) {
               start = mid + 1;
           } else {
               end = mid - 1;
           }
       }
   }

   return -1;
};