Find Peak Element

mediumSave

ArrayBinary Search

Given an array of integers nums, find a peak element and return its index. A peak element is an element that is strictly greater than its neighbors. For array boundaries, we only consider one neighbor (only the previous neighbor for the first element and only the next neighbor for the last element).

Example 1

Input

[
  1,
  3,
  4,
  3,
  1
]

Output

Explanation. Element at index 2 is 4, which is greater than both its neighbors (3 and 3).

Example 2

Input

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

Output

Explanation. Element at index 5 is 6, which is greater than its neighbor 5 and greater than its other neighbor 4.

Example 3

Input

Output

Explanation. Element at index 1 is 20, which is a peak as it is greater than both its neighbors (10 and 15).

Example 4

Input

[
  3,
  2,
  1
]

Output

Explanation. Element at index 0 is 3, which is greater than its only neighbor 2.

Example 5

Input

[
  1,
  10,
  5
]

Output

Explanation. Element at index 1 is 10, which is a peak as it is greater than both its neighbors (1 and 5).

Follow-up: Can you implement this solution to run in O(log n) time complexity?

Constraints:

The input array will not be empty and will contain at least one element. You may assume that `nums` does not contain any duplicates.

Views: 3