[leetcode 33] Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums 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]).

If target is found in the array return its index, otherwise, return -1.

 

본래 오름차순인 배열이 특정 위치를 중심으로 회전되어 있다. 주어진 target의 위치를 찾아라.

 

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

 

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is guranteed to be rotated at some pivot.
• -10^4 <= target <= 10^4

풀이:

- 문제 이해가 좀 어려웠다.

- 어렵게 생각안하고 모든 배열을 순서대로 돌아도 통과한다. 심지어 소요 시간도 동일함

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        //pivot을 기준으로 회전된 수열이 있다.
        // 이 상태에서 pivot이 있는지 확인하기
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
};

 

- 또 다른 풀이: 이분탐색 사용

- begin과 end를 사용하여 begin end의 범위를 점차 좁혀 나간다. 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int n = nums.size();
        
        if(n == 1 && nums[0] == target){
            return 0;
        }
        
        if(nums[0] > target && nums[n-1] < target){
            return -1;
        }
        
        int begin = 0, end = n-1;
        while(begin < end){

            if(nums[begin] == target){
                return begin;
            }
            
            if(nums[end] == target){
                return end;
            }
            
            if(nums[begin] < target){
                begin ++;
            }else {
                end --;
            }
        }
        return -1;
    }
};