162. Find the peak [binary search]

Hits: 0

A peak element is an element whose value is strictly greater than its left and right neighbors.

Given an integer array nums, find the peak element and return its index. The array may contain multiple peaks, in which case the position of any one of the peaks is returned.

You can assume nums[-1] = nums[n] = -∞ .

You have to implement [an] O(log n) algorithm to solve this problem.

Example 1:

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

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

hint:

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

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int mid,l=0,r=nums.size()-1;
        while(l<r)
        {
            mid = (l+r)/2;
            if(nums[mid]<nums[mid+1])
            {
                l = mid+1;
            }
            else
            {
                r = mid;
            }
        }
        return l;
    }
};

You may also like...

Leave a Reply

Your email address will not be published.