852. Peak Index in a Mountain Array
https://leetcode.com/problems/peak-index-in-a-mountain-array/
Let's call an array
A a mountain if the following properties hold:A.length >= 3- There exists some
0 < i < A.length - 1such thatA[0] < A[1] < ... 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[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
Example 1:
Input: [0,1,0] Output: 1
Example 2:
Input: [0,2,1,0] Output: 1
Note:
3 <= A.length <= 100000 <= A[i] <= 10^6- A is a mountain, as defined above.
----
Intuition
Linear scan is trivial
To do better than linear we need to use info that this is a mountain array, so sorted increasing till the peak, then sorted descending
---
Standard binary search - loop termination l <= h
if arr[mid] > arr[mid - 1] => we found potential answer, save it, continue search on other side l = mid + 1 *
else mid is on decreasing half, certainly not a candidate, search other side h = mid - 1
* to consider first element or with mid == 0
---
Standard binary search - loop termination l <= h
if arr[mid] > arr[mid - 1] => we found potential answer, save it, continue search on other side l = mid + 1 *
else mid is on decreasing half, certainly not a candidate, search other side h = mid - 1
* to consider first element or with mid == 0
---
Variant of binary search
Normally binary search exits when l > r, and there's an exact match A[mid] == target
Here we are not looking for a target, so A[mid] == target branch doest not apply, so we also drop the = from while (l <= h) loop boundary to terminate the loop
if A[mid + 1] > A[mid] - mid is still in increasing half => l = mid + 1
if A[mid + 1] < A[mid] - mid could be the peak or on decreasing side so don't discard mid => h = mid
---
Time - O(log n)
Space - O(1)
