# 852-peak-index-in-a-mountain-array

## Question

https://leetcode.com/problems/peak-index-in-a-mountain-array/description/

Let's call an array A a mountain if the following properties hold:

A.length >= 3 There exists some 0 < i < A.length - 1 such that A < A < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1] Given an array that is definitely a mountain, return any i such that A < A < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example:

``````Input: [0,1,0]
Output: 1

Input: [0,2,1,0]
Output: 1
``````

Note:

3 <= A.length <= 10000 0 <= A[i] <= 10^6 A is a mountain, as defined above.

## Thought Process

1. Binary Search
1. Since there is only one peak, we can use binary search to successively cut the search range by half
2. The boundaries are lo = 1, hi = A.length - 2
3. We compare A[mi] to A[mi + 1]
4. If A[mi] < A[mi + 1], the peak lies on the right, so lo = mi + 1
5. Else hi = mi
6. Time complexity O(logn)
7. Space complexity O(1)

## Solution

``````class Solution {
public int peakIndexInMountainArray(int[] A) {
int lo = 1, hi = A.length - 2;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (A[mi] < A[mi + 1]) lo = mi + 1;
else hi = mi;
}
return lo;
}
}
``````