Binary Search Searching a sorted array
238. Find Peak Element
You are given an array of integers nums. Return the index of any peak in it.
An element is a peak when it is larger than each of its neighbours. Every position outside the array counts as
−∞, so an element at either end only has to be larger than the one neighbour it has. In [1, 4, 2, 7], the
peaks are 4 at index 1 and 7 at index 3.
An array can have several peaks, and any of them is a correct answer. The result shows a peak when the index
you return is one. Otherwise it says what is wrong, such as 2 is not a peak or 9 is outside the array.
Aim for O(log n) time.
Example 1
Input: nums = [4, 11, 7, 9, 15, 12, 3, 8]
4Explanation: nums[4] = 15 is larger than 9 on its left and 12 on its right. Index 1 (11, between 4 and 7) and index 7
(8, at the end, with only 3 beside it) are peaks too, and any of the three is correct.
Example 2
Input: nums = [0, -4, -1, -9]
2Explanation: −1 is larger than −4 and −9. Index 0 is also a peak: 0 is larger than −4, its only neighbour, and the position to its left counts as −∞.
Example 3
Input: nums = [-2147483648]
0Explanation: A single element has no neighbours, so it is a peak, even though it is the smallest value allowed.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-231 ≤ nums[i] ≤ 231 − 1nums[i] ≠ nums[i + 1]for every validi
Clarifying questions
What you would ask an interviewer before writing any code.