This algorithm finds the peak element in a mountain array using binary search. A mountain array increases to a peak and then decreases.
Steps
- Initialize
l = 0andr = arr.length - 1 - Use binary search:
- If
arr[m + 1] > arr[m], peak is to the right →l = m + 1 - Else peak is at
mor to the left →r = m - When loop ends,
l(orr) is the peak index
Dry Run
Input: [0,1,0] → Output: 1
Input: [0,2,1,0] → Output: 1
Input: [0,10,5,2] → Output: 1
Time & Space Complexity
- Time: O(log n)
- Space: O(1)
var peakIndexInMountainArray = function(arr) {
let l = 0;
let r = arr.length - 1;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (arr[m + 1] > arr[m]) {
l = m + 1;
} else {
r = m;
}
}
return r;
};
int peakIndexInMountainArray(vector& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m + 1] > arr[m]) {
l = m + 1;
} else {
r = m;
}
}
return r;
}
int peakIndexInMountainArray(int* arr, int arrSize) {
int l = 0, r = arrSize - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m + 1] > arr[m]) {
l = m + 1;
} else {
r = m;
}
}
return r;
}
public int peakIndexInMountainArray(int[] arr) {
int l = 0, r = arr.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m + 1] > arr[m]) {
l = m + 1;
} else {
r = m;
}
}
return r;
}
def peakIndexInMountainArray(arr):
l, r = 0, len(arr) - 1
while l < r:
m = l + (r - l) // 2
if arr[m + 1] > arr[m]:
l = m + 1
else:
r = m
return r
public int PeakIndexInMountainArray(int[] arr) {
int l = 0, r = arr.Length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m + 1] > arr[m]) {
l = m + 1;
} else {
r = m;
}
}
return r;
}
