Problem Statement

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Constraints:

• 1 <= nums.length <= 1000
• 231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

Problem Link

Find Peak Element - LeetCode

Code

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        
        int n = nums.size();
        
        if(n==1)
            return 0;
        
        int low = 0, high = n-1;
        
        while(low<=high)
        {
            int mid = (low+high)/2;
            
            if(mid==0)//if mid is the first element of the array
            {
                if(nums[mid]>nums[mid+1])//just check its right neighbour
                    return mid;
                else//if right neighbour is greater
                    low = mid + 1;
            }
            else if(mid==n-1)//if mid is the last element of the array
            {
                if(nums[mid]>nums[mid-1])//just check its left neighbour
                    return mid;
                
                else//if left neighbour is greater
                     high = mid - 1;
            }
            else
            {
                if(nums[mid]>nums[mid+1]&&nums[mid]>nums[mid-1])//check both neighbours
                    return mid;
                
                else if(nums[mid-1]>nums[mid+1])//if left neighbour is greater than right 
								//we go right
                    high = mid - 1;
                
                else//if right neighbour is greater than left 
								//we go left
                    low = mid + 1;
                    
            }
            
            
        }
        
        return -1;
        
    }
};

Another solution

class Solution {
public:
    int findPeakElement(vector<int>& nums) {

        int n = nums.size();

        if(n==1) return 0;

        if(nums[0]>nums[1]) return 0;

        if(nums[n-1]>nums[n-2]) return n-1;

        int low = 1, high = n-2;

        while(low<=high) {
            int mid = (low+high)/2;

            if(nums[mid]>nums[mid+1]&&nums[mid]>nums[mid-1]) {
                return mid;
            } else if(nums[mid]<nums[mid+1]) {
                low = mid+1;
            } else {
                high = mid-1;
            }

           
        }

        return -1;

       
    }
};