Find Peak Element

mediumSave

ArrayBinary Search

A peak element is an element that is strictly greater than its neighbors. Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peak elements, return the index to any of them. You may imagine that nums[-1] = nums[n] = -infinity.

Example 1

Input

[
  "[1,2,3,1]"
]

Output

Explanation. 3 is a peak element because it is greater than its neighbors (2 and 1). Its index is 2.

Example 2

Input

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

Output

Explanation. There are multiple peak elements. 2 (at index 1) is a peak. 6 (at index 5) is a peak. 5 is a valid output, as the problem allows returning the index to any peak element. 6 is greater than its neighbors (5 and 4).

Example 3

Input

[
  "[3,4,3,2,1]"
]

Output

Explanation. 4 is a peak element because it is greater than its neighbors (3 and 3). Its index is 1.

Example 4

Input

[
  "[1]"
]

Output

Explanation. With only one element, considering `nums[-1]` and `nums[n]` as -infinity, 1 is a peak element. Its index is 0.

Example 5

Input

[
  "[1,2]"
]

Output

Explanation. 2 is a peak element because it is greater than 1 and `nums[2]` (which is -infinity). Its index is 1.

Example 6

Input

[
  "[2,1]"
]

Output

Explanation. 2 is a peak element because it is greater than `nums[-1]` (which is -infinity) and 1. Its index is 0.

Follow-up: Can you write a solution that runs in O(log n) time?

Constraints:

* `1 <= nums.length <= 1000` * `-2^31 <= nums[i] <= 2^31 - 1` * `nums[i] != nums[i+1]` for all valid `i`.

Views: 2