find-peak-element

gistfile1.cpp

/*
https://leetcode.com/problems/find-peak-element/

O(log n)
key point: getting a sense of that current maximum is a strong nominate of local maximum.

1. pick middle of the give subarray
2. compare both neighbor of current maximum
3. ignore smaller side. (why? -> current maximum could be a local maximum)
4. 1->3 iterate until the length of the given subarray is less than 1 
*/

class Solution {
public:
    int findPeakElement(const vector<int> &num) {
        int left = 0;
        int right = num.size()-1;
       
        while(abs(left-right) > 1) {
            int mid = (left+right)/2;
            if(num[mid] > num[mid-1] && num[mid] > num[mid+1]) {
                
                return mid;
            } else if( num[mid-1] > num[mid]) {
                right = mid-1;   
            } else {
                left = mid+1;
            }
        }
        
        if(num[left] > num[right]) {
            return left;
        } else {
            return right;
        }
        
    }
};