Peak Index in a Mountain Array via Ternary Search

A mountain array is an array of n distinct integers (n >= 3) that strictly increases from the first element up to a single peak index, then strictly decreases down to the last element. Given such an array, find the index of the peak element using a ternary-search-style divide-and-conquer approach that discards roughly one third of the remaining search space at each step, achieving O(log n) time.

Input: The first line contains the integer n. The second line contains n space-separated integers forming a mountain array. Output: Print a single integer: the 0-based index of the peak element.

3 <= n <= 10^5 The array strictly increases then strictly decreases around exactly one peak index -10^9 <= a[i] <= 10^9, all values distinct

This is a great problem for comparing TWO different divide-and-conquer strategies (binary vs ternary search) for the SAME unimodal-array structure - both work, but recognizing when one is simpler than the other is a valuable practical skill.

Find the peak of a 'mountain' array (strictly increasing then strictly decreasing) using a divide-and-conquer search that discards a third of the range each step. Brute force: Scan the entire array linearly, checking each element against its neighbors to find where the climb turns into a descent - this costs O(n), more than necessary given the mountain shape's exploitable structure. Optimised: Ternary search exploits the UNIMODAL (single peak, rises then falls) shape of the array - comparing two interior points at each step reveals which THIRD of the range CANNOT contain the peak (since one side is still strictly climbing), letting each step discard a third of the remaining search space, achieving O(log n) time overall (though with a slightly larger constant factor than binary search's halving).

1. Pick TWO interior points that split the current search range into three roughly equal parts, and compare the VALUES there. 2. If the LEFT of the two points has a SMALLER value than the right one, the peak cannot lie in the LEFTMOST third (the array is still climbing there) - discard it. 3. Symmetric reasoning discards the RIGHTMOST third otherwise; keep shrinking the range until only a handful of candidates remain, then scan them directly.

Time: O(log n) - each step discards roughly a third of the remaining search range. Space: O(1) - just a few pointer variables.

The minimal mountain size n = 3, where the peak is necessarily at index 1; the peak located very close to either end of a large array.

Be ready to mention that a MODIFIED BINARY SEARCH (comparing a single midpoint to its immediate neighbor, deciding which half to search) actually solves this same problem with a cleaner halving-based approach - ternary search works too, but binary search is often the simpler, more commonly expected solution for this specific mountain-peak problem.