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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int peakIndexInMountainArray(int[] A) { | |
| int l = 0, h = A.length - 1; | |
| int ans = -1; | |
| while (l <= h) { | |
| int mid = l + (h - l) / 2; | |
| if (mid == 0 || A[mid] > A[mid - 1]) { | |
| ans = mid; | |
| l = mid + 1; | |
| } else { | |
| h = mid - 1; | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int peakIndexInMountainArray(int[] A) { | |
| int l = 0, h = A.length - 1; | |
| while (l < h) { | |
| int mid = l + (h - l) / 2; | |
| if (A[mid + 1] > A[mid]) { | |
| l = mid + 1; | |
| } else if (A[mid + 1] < A[mid]) { | |
| h = mid; | |
| } | |
| } | |
| return h; | |
| } | |
| } |
