리트코드 153 회전 정렬 배열에서 최소값 찾기 c++ // 이분탐색

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

1. 의사코드

우리는 보물인 0을 찾는것이다.

[4 5 6 7 0 1 2]

st      m       en

mid>en이면, 보물이 우측에 있는것이다. -> st=mid+1

[0 1 2]에서

mid 0 <en 2이면,   보물이 좌측에 있는것이다. -> en=mid; //mid-1아님

[0 1]에서

mid=0 < en=1 -> 보물이 좌측 -> en=0;

en과 st가 0으로 수렴했고, 그곳이 보물이다!

 

2. 전체코드

class Solution {
public:
    int findMin(vector<int>& nums) {
        int st=0,en=nums.size()-1;
        while(st<en){
            int mid=(st+en)/2;
            if(nums[mid]<nums[en]){
                en=mid;
            }
            else{
                st=mid+1;
            }
        }
        return nums[st];
    }
};