162.Find Peak Element

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

Given an input array wherenum[i] ≠ num[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 thatnum[-1] = num[n] = -∞.

For example, in array[1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Your solution should be in logarithmic complexity.

Method 1 O(log n) time, O(1) space.

• Since both sides are -inf, do a binary search starting from the middle element and examine its neighbors:
  • If mid element is greater than both of its neighbors, return mid index.
  • If mid element is in an ascending curve, look at later half of the array.
  • If mid element is in an descending curve, look at first half of the array.

class Solution(object):
    def findPeakElement(self, nums):
        low, high = 0, len(nums)-1
        while low <= high:
            mid = (high+low)/2
            left = nums[mid-1] if mid - 1 >= 0 else float('-inf')
            right = nums[mid+1] if mid + 1 < len(nums) else float('-inf')
            if left < nums[mid] > right:
                return mid
            elif left < nums[mid] < right:
                low = mid + 1
            else:
                high = mid - 1
        return mid