Leetcode[day19] -Search in Rotated Sorted Array

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(log n).

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

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 오름 차순의 배열이 주어질 때, 특정 수만큼 shift 되어져있다.

그 때, input으로 주어진 target을 찾고, 찾을 수 없다면 -1을 리턴해라.

 - 특정 pivot을 정해놓고, 왼쪽 오른쪽을 탐색해야 한다고 생각을 했다.

 - 그런데, 특정 수만큼 배열이 이동되어 있다는 것을 잘 생각해야 한다.

 

 

2. 알고리즘 작성 중, 어려운 점

 

 - 이동된 배열을 비교하는 방법을 어떻게 해야하는가?

 

3. 내가 작성한 알고리즘

 

 

class Solution {
    public int search(int[] nums, int target) {
        int answer = binarySearch(nums, target, 0, nums.length - 1);
        return answer;
    }
    
    private int binarySearch(int[] nums, int target, int left, int right){        
        int pivot = (left + right) / 2;
        if(left > right){
            return -1;
        }
        else if(nums[pivot] == target){
            return pivot;
        }
        if(nums[left] <= nums[pivot]){
            if(nums[left] <= target && nums[pivot] > target){
                return binarySearch(nums, target, left, pivot - 1);
            }
            else{
                return binarySearch(nums, target, pivot+1, right);
            }    
        }else{
            if(nums[pivot] < target && nums[right] >= target){
                return binarySearch(nums, target, pivot + 1, right);
            }
            else{
                return binarySearch(nums, target, left, pivot-1);
            }  
        }
    }
}

4. 내가 작성한 알고리즘 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3304/

Explore - LeetCode