[JavaScript] 33. Search in Rotated Sorted Array - 쉬운설명 바이너리 서치 활용

33. Search in Rotated Sorted Array

 

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

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

 

Example 1:

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

 

Example 2: 

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

 

Example 3: 

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

 

계획

문제 해결 전략

 

일단 sorted였던 array가 rotated됬는데 얼마나 roated됬는지 알수없다 가정을 한다. 

못찾으면, -1 

찾으면 그 인덱스 찾아서 리턴

O(log n )속도로 만들어야하기때문에 loop로 구현할수없습니다. 

 

 

구현 전략

 

binary search를 이용해서 

 

해설

var search = function(nums, target) {
	//비어있는 array라면 -1을 리턴
    if (nums.length === 0) return -1
    //길이가 1인 array라면 array의 0위치에있는 값이 타겟과 같다면 0을 리턴 아니면 -1리턴 
    else if (nums.length === 1) return nums[0] === target ? 0 : -1;

    //바이너리 서치를 사용하여, 가장작은 넘버를 찾는다.    
    let minIndex = findMinIndex(nums, 0, nums.length - 1);  

    //만약 min index가 target과 같다면,그걸 리턴
    if (nums[minIndex] === target) return minIndex;

	//Default lo and hi values will remain if the array wasn't rotated (minIndex == 0)
    let lo = 0, hi = nums.length - 1;

	//If target is less than first value, we know it's to the right of the rotation
    if (target < nums[0]) lo = minIndex;
    
	//Otherwise search the left
    else if (minIndex !== 0) hi = minIndex;

	//Binary Search for target    
    while (lo <= hi) {
        let mid = Math.floor((lo + hi)/2);
    
        if (target === nums[mid]) return mid;
        else if (target < nums[mid]) hi = mid - 1;
        else lo = mid + 1;
    }
    
    return -1;
};

function findMinIndex(arr, lo, hi) {// nums, 0 , nums.length
//If the low is less than the high index value, array wasn't rotated
    if (arr[lo] < arr[hi]) return 0;
    
    while (lo <= hi) {
        let mid = Math.floor((lo + hi)/2);
        
        if (arr[mid] > arr[mid + 1]) return mid + 1;
        else {
            //Examine the left
            if (arr[mid] < arr[lo]) hi = mid - 1;
            //Examine the right
            else lo = mid + 1;
        }
    }
    return 0;
}