Medium · Slope Binary Search
Understand → Visualise → Practice.
Return an index whose value is not smaller than its neighbours; outside values count as negative infinity.
If nums[mid] < nums[mid + 1], the slope rises to the right, so a peak must exist to the right; otherwise one exists at mid or to its left.
Start with the whole array.
If nums[mid] < nums[mid + 1], set lo = mid + 1; otherwise hi = mid.
When lo == hi, that index is a peak.
O(log n) time and O(1) space.
Comparing with nums[mid − 1] as well complicates the bounds; one comparison with the right neighbour is enough.
Read the full guides first: Sorting Algorithms and Their Trade-offs, Binary Search and Boundary Finding.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.