Find Peak Element

ArrayBinary Search

Given an integer array nums, where the array may contain several peaks, find any peak element and return its index. A peak element is defined as an element that is greater than its neighbors.

Note:

The array may contain multiple peaks, in that case, returning the index to any peak is acceptable.
The array will always contain at least one element.
If the element is at the boundary of the array (i.e., first or last element), it only needs to be greater than its one adjacent neighbor to be considered a peak.

Example 1

Input

[
  1,
  3,
  2,
  4,
  1
]

Output

Explanation. The element at index 3 is 4, which is greater than its neighbors (2 and 1). Thus, it is a peak element.

Example 2

Input

[
  5,
  4,
  3,
  2,
  1
]

Output

Explanation. The first element (5) is only checked against its one neighbor (4) and is larger. Thus, it is a peak element.

Example 3

Input

[
  1,
  2,
  3,
  4,
  5
]

Output

Explanation. The last element (5) is only checked against its one neighbor (4) and is larger. Thus, it is a peak element.

Follow-up: Can you implement your solution with a time complexity better than O(n)?

Constraints:

- The input array will contain at least one element. - The values in the array are all integers. - You may assume no duplicates for simplicity.

Views: 2