Problem


Key Idea

์ด์ง„ํƒ์ƒ‰์œผ๋กœ \(nums[m]\) ๊ฐ’๊ณผ ์–‘ ์˜†์˜ ๊ฐ’์„ ๋น„๊ตํ•ด์ค€๋‹ค.

  1. \(nums[m-1] \gt nums[m]\) ์ด๋ฉด:
    index \(m\) ์™ผ์ชฝ์— \(peak\)๊ฐ€ ์กด์žฌ.
    r <- m;
    
  2. \(nums[m] \lt nums[m+1]\) ์ด๋ฉด:
    index \(m\) ์˜ค๋ฅธ์ชฝ์— \(peak\)๊ฐ€ ์กด์žฌ.
    l <- m+1;
    
  3. ๋‘˜๋‹ค ์•„๋‹ˆ๋ฉด: index \(m\) ์ž์ฒด๊ฐ€ \(peak\).
    return m;
    


Implementation

/**
 * written: 2021. 12. 29. Wed. 16:05:01 [UTC+9]
 * jooncco์˜ mac์—์„œ.
 **/

typedef vector<int> vi;

class Solution {
public:
    int findPeakElement(vi &nums) {
        int n= nums.size();
        // nums[-1]๊ณผ nums[n]์ด -โˆž ์ด๋ฏ€๋กœ size๊ฐ€ 1์ด๋ฉด ์ž์ฒด๊ฐ€ peak
        if (n == 1) return 0;
        
        int l= 0, r= n-1;
        while (l < r) {
            int m= l+(r-l)/2;
            if (m > 0 && nums[m] < nums[m-1]) r= m;
            else if (m < n-1 && nums[m] < nums[m+1]) l= m+1;
            else return m;  // peak๋ฅผ ์ฐพ์•˜์œผ๋‹ˆ ๋ฐ”๋กœ return.
        }
        // l == peak index
        return l;
    }
};

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

Leave a comment