162. Find Peak Element in O(logn)

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

Given an input arraynums, wherenums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

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

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: 1 or 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.

Thoughts:

1. Using binary search to compare two midpoints, the larger one being the new searching boundary

Code: Iterative

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int low = 0, high = nums.size()-1;
        while(low< high){
            int mid1 = (low + high)/2;
            int mid2 = mid1 + 1;
            if(nums[mid1] < nums[mid2]){
                low = mid2;
            }
            else{
                high = mid1;
            }
        }

        return low;
    }
};

Code: Recursive:

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        return binarySearch(nums, 0, nums.size()-1);
    }

    int binarySearch (vector<int>& nums, int low, int high){
        if(low == high) return low; // binary search converges low and high points together in the very end
        int mid1 = (low + high) /2;
        int mid2 = mid1 + 1;
        if (nums[mid1] > nums[mid2]){
            return binarySearch(nums, low, mid1);
        }
        else {
            return binarySearch(nums, mid2, high);
        }
    }
};

from gangan's post