Problem


Key Idea

์ด์ง„ํƒ์ƒ‰์œผ๋กœ \(nums[l]\), \(nums[m]\), \(nums[r]\) ๊ฐ’์„ ๋น„๊ตํ•ด์ค€๋‹ค.

  1. \(nums[l] \le nums[m]\) ์ด๋ฉด:
    ์ตœ์†Ÿ๊ฐ’์€ index \(m\)๋ณด๋‹ค ์˜ค๋ฅธ์ชฝ์— ์žˆ๋‹ค.
    l <- m+1;
    
  2. ์•„๋‹ˆ๋ฉด:
    ์ตœ์†Ÿ๊ฐ’์€ \(nums[m]\) ์ž์ฒด์ด๊ฑฐ๋‚˜, index \(m\)๋ณด๋‹ค ์™ผ์ชฝ์— ์žˆ๋‹ค.
    r <- m;
    


Implementation

/**
 * written: 2021. 12. 29. Wed. 15:51:07 [UTC+9]
 * jooncco์˜ mac์—์„œ.
 **/

typedef vector<int> vi;

class Solution {
public:
    int findMin(vi &nums) {
        int n= nums.size();
        // size๊ฐ€ 1์ด๊ฑฐ๋‚˜ rotate๊ฐ€ ์ผ์–ด๋‚˜์ง€ ์•Š์€ ๊ฒฝ์šฐ
        if (n == 1 || nums[0] < nums[n-1]) return nums[0];
        
        int l= 0, r= n-1;
        while (l < r) {
            int m= l+(r-l)/2;
            // nums[l], nums[m], nums[r] ๊ฐ’์„ ๋น„๊ต.
            // nums[l] < nums[r]์ธ ๊ฒฝ์šฐ์— ๋Œ€ํ•œ ์˜ˆ์™ธ์ฒ˜๋ฆฌ๋ฅผ ํฌํ•จ
            if (nums[l] <= nums[m] && nums[l] > nums[r]) l= m+1;
            else r= m;
        }
        // l: ์ตœ์†Œ index
        return nums[l];
    }
};

  • Time: \(O(\log n)\)

Leave a comment