Find Peak Element

mediumSave

ArrayBinary Search

Given an array of integers nums, where nums[i] does not equal nums[i + 1] for any 'i', find a peak element and return its index. A peak element is an element that is greater than its neighbors.

For example, in the array 3, 4, 3, 2, 1, 4 is a peak element because it is greater than its neighbors 3 and 3.

Note:

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

Example 1

Input

[
  1,
  2,
  3,
  1
]

Output

Explanation. 3 is the peak element because it is greater than its neighbors 2 and 1.

Example 2

Input

[
  1,
  2,
  1,
  3,
  5,
  6,
  4
]

Output

Explanation. 6 is a peak element because it is greater than its neighbors 5 and 4.

Example 3

Input

[
  3,
  4,
  5,
  6
]

Output

Explanation. 6 is the peak element as it is not smaller than its neighbor 5 (and there's no neighbor on the right side).

Example 4

Input

[
  6,
  5,
  4,
  3
]

Output

Explanation. 6 is the peak element as it is not smaller than its neighbor 5 (and there's no neighbor on the left side).

Follow-up: Can you implement your solution with a logarithmic runtime complexity (i.e., O(log n))?

Constraints:

The input will be a non-empty array containing integers. The array may have one element.

Views: 2