Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
815 B
1
Indexable
Never
/* 
there is a concept called binary search on answer, the sole idea of binary search in not only about finding a target in a sorted array, but to half the sample space after each decision.
 */
 //imagine slopes like we did in DSP
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int n= nums.size();
        if(nums[0] >nums[1]) return 0;
        if(nums[n-1] > nums[n-2]) return n-1;
        int s=0,e=nums.size()-1;
        while(s<=e){
            int mid1=s+(e-s)/2;
            int mid2=mid1+1;
            if(nums[mid1] >nums[mid1-1] && nums[mid1] > nums[mid1+1]) return mid1;

            if(nums[mid1] <nums[mid2]){
                s=mid1 +1;
            }else{
                e=mid1;
            }
        }
        return -1;    
    }
};