Peak Element Finder

ArrayBinary Search

Given an array of integers, find a peak element. A peak element is an element which is greater than its neighbors. For array elements at the boundaries, only one neighbor is considered for comparison.

Example 1

Input

[
  1,
  3,
  20,
  4,
  1,
  0
]

Output

Explanation. Element 20 at index 2 is greater than both its neighbors 3 and 4. Although other peak elements may exist, index 2 is a valid answer.

Example 2

Input

Output

Explanation. Element 20 at index 2 is greater than its neighbor 15. Element 20 is also the highest so it's a clear peak.

Example 3

Input

Output

Explanation. Element 25 at index 4 is a peak as it has only one neighbor (20) and it is greater than 20. Being at the end of the array, index 4 is a valid peak.

Example 4

Input

[
  6,
  6,
  6,
  6
]

Output

Explanation. All elements are the same. Any index can be considered a peak as no neighbor is greater. Here, index 0 is chosen arbitrarily.

Follow-up: Can you implement the solution to run in logarithmic time complexity?

Constraints:

The input array will contain at least one element. The array may contain multiple peaks, return the index of any one of the peaks.

Views: 2