[LeetCode] 153. Find Minimum in Rotated Sorted Array 문제풀이

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

Find Minimum in Rotated Sorted Array - LeetCode

문제 내용

정렬된 배열에 로테이션된 상황이 주어졌을 때,

최소값을 찾는 문제

 

Example 1:

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

 

문제 풀이

바이너리 서치로 쉽게 풀수 있다.

바이너리 서치 어떻게 적용시킬지 생각하는게 어려운 문제이다.

 

조건이 left 방향으로 shift가 된다.

배열의 끝에 있는 값이 항상 최소값 보다 큰 값이 된다.

최소값은 오른쪽에서 왼쪽으로 가면서 커지는 부분에 위치해있다.

 

바이너리 서치 사용하는 팁

배열 끝 요소를 기준으로 작은 값을 F, 큰 값을 T 라고 하면

F->T 로 바뀔때의 F가 최소값이 된다.

 

class Solution {
public:
    int findMin(vector<int>& nums) {
        int s = 0;
        int e = nums.size()-1;
        int ans = 0;
        int target = nums[e];
        
        while(s <= e) {
            int m = (s+e)>>1;
            if (nums[m] <= target) {
                ans = m;
                e = m-1;
            } else {
                s = m+1;
            }
        }
        return nums[ans];
    }
};