Problem
Key Idea
์ด์งํ์์ผ๋ก \(nums[l]\), \(nums[m]\), \(nums[r]\) ๊ฐ์ ๋น๊ตํด์ค๋ค.
- \(nums[l] \le nums[m]\) ์ด๋ฉด:
์ต์๊ฐ์ index \(m\)๋ณด๋ค ์ค๋ฅธ์ชฝ์ ์๋ค.l <- m+1;
- ์๋๋ฉด:
์ต์๊ฐ์ \(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