[ leetcode 문제풀이 ] Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

(Search in Rotated Sorted Array 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Search in Rotated Sorted Array 문제 설명 >

 

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.

 

(서로 다른 값을 가진) 오름차순으로 정렬된 정수 배열 nums 가 있다. 여러분이 작성할 함수에 전달되기 전에 nums는 어떠한 pivot index k 만큼 회전해 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 가 되도록 하였다. 

 

회전이 가해진 후의 nums 배열과 정수 target이 주어졌을 때, nums 에 target이 있으면 target의 index를 리턴하고, 만약 없으면 -1을 리턴하여라. 반드시 O(log n) 시간복잡도를 가진 알고리즘으로 작성하여라.

 

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 1 ≤ nums.length ≤ 5000, -10^4 ≤ nums[i] ≤10^4 과 nums의 모든 원소는 서로 다르다는 것이다.

 

 

 

---

< Search in Rotated Sorted Array 문제 접근 >

 

O(log n) 시간복잡도의 코드를 작성하라는 것은 이진탐색으로 target을 찾으라는 것이다. < Find Minimum in Rotated Sorted Array > 문제에서 가장 작은 원소를 찾는 알고리즘을 구현했기 때문에 최소 원소의 위치를 아는 상태에서 이진 탐색을 하기란 굉장히 쉽다. ( Find Minimum in Rotated Sorted Array 알고리즘은 아래 링크 참고해주시면 됩니다.)

[ leetcode 문제풀이 ] Find Minimum in Rotated Sorted Array

 

이진탐색은 최소 원소의 위치만큼 shift한 상태로 진행해주면 된다. 이를 코드로 나타내면 다음과 같다. (Cpp 사용)

 

int findMinIndex(vector<int>& nums) {
    int low = 0;
    int high = nums.size();
    while(low < high){
        int mid = (low + high) / 2;
        if(nums[low] < nums[mid])
            low = mid;
        else
            high = mid;
    }
    return (low+1)%nums.size();
} // from problem 'Find Minimum in Rotated Sorted Array'

int search(vector<int>& nums, int target) {     
    int MinIndex = findMinIndex(nums);
        
    int n = nums.size();
    int low = 0, high = n-1;	
    while(low <= high){
        int mid = (low + high) / 2;		// low, high, mid는 원소의 크기 순번임
        int MiddleIndex = (MinIndex + mid)%n; 	// 크기 순서에서 index 값으로 변환
        if(nums[MiddleIndex] == target)
            return MiddleIndex;
        if(nums[MiddleIndex] < target)
            low = mid+1;
        else
            high = mid-1;
    }
    return -1;       	// while loop을 빠져나온 경우는 target을 만족하는 원소가 없는 경우
}

 

Find Minimum in Rotated Sorted Array를 풀고 나니 이번 문제는 꽤나 간단하게 해결되었다.