85. Find a Peak Element in an Array

Given an array of n integers, find the index of a peak element - one that is greater than or equal to both of its neighbors (array boundaries count as negative infinity). If multiple peaks exist, print the index of the first one found scanning left to right.

Input: The first line contains an integer n. The second line contains n space-separated integers. Output: Print a single integer - the index of a peak element (the first one found scanning left to right if multiple exist).

1 <= n <= 10^5

This problem only asks for ANY peak, not necessarily the largest one - this relaxed requirement is precisely why binary search (which finds A peak quickly) works, whereas finding the GLOBAL maximum peak would require a full linear scan in the worst case.

Find any element that's greater than or equal to both of its immediate neighbors (treating the array's edges as bordering negative infinity). Brute force: Scan the array linearly, checking each element against both its neighbors - this costs O(n), correct but doesn't exploit the guaranteed EXISTENCE of a peak (given the boundary convention) to search faster. Optimised: Moving toward whichever neighbor is LARGER at each step is guaranteed to eventually reach a peak, since you're always moving toward increasing values, and the array's boundaries (treated as negative infinity) guarantee this ascent can't run off the edge without hitting a peak - this lets binary search find A peak (not necessarily the global maximum) in O(log n).

This problem specifically asks for the first (leftmost) peak when scanning left to right, which rules out the classic O(log n) binary-search-for-a-peak trick: that technique only guarantees finding some peak, and can easily land on one that isn't the leftmost. Worse, a strictly increasing array has its only peak at the very last index, which forces any correct algorithm to examine the whole array in the worst case, so O(n) is a provable lower bound here, not just a limitation of a particular technique. The single left-to-right ascent-tracking scan above is therefore already asymptotically optimal, using O(1) extra space and no more comparisons than necessary. Time: O(n) Space: O(1)

Sweep left to right comparing only each element to the next one, arr[i] vs arr[i+1], instead of checking both neighbors of every index separately. The first index where the sequence stops strictly increasing (arr[i] >= arr[i+1]) is a peak, and if the array increases all the way to the end, the last index is the peak (its right boundary counts as negative infinity). This halves the number of comparisons versus checking both neighbors at each index, since each adjacent pair is examined exactly once. Time: O(n) Space: O(1)

For every index i from left to right, independently check whether arr[i] is greater than or equal to arr[i-1] (or there is no left neighbor) and arr[i] is greater than or equal to arr[i+1] (or there is no right neighbor), and stop at the first i where both hold. This directly implements the peak definition and the required left-to-right tie-break, checking each neighbor pair explicitly even though adjacent indices re-examine overlapping elements. Time: O(n) Space: O(1)

1. A single-element array is trivially always a peak. 2. Binary search: at a candidate mid, compare it to its right neighbor. 3. If mid's value is smaller than its right neighbor, a peak is guaranteed to exist somewhere to the RIGHT - search there; otherwise, a peak is guaranteed to exist at mid or to its LEFT.

Time: O(log n) - a binary search that always moves toward the larger neighbor. Space: O(1) - just a few pointer variables.

Test n = 1 (always a peak), a strictly increasing or strictly decreasing array (peak at an end), and n = 10^5 for performance.

Be ready to explain clearly why a peak is GUARANTEED to exist (the boundary convention of treating out-of-array as negative infinity) - this existence guarantee is exactly what makes the greedy 'move toward the bigger neighbor' binary search provably correct.