Practice › Binary Search
Peak of Mountain Array
Medium · Binary Search · Asked at Amazon, Google, Microsoft
The array strictly increases and then strictly decreases. Print the index (0-based) of the peak.
Input
First line: n. Second line: n integers.
Output
The peak index.
Constraints
- 3 ≤ n ≤ 10^5
- The peak is never the first or last element
Example 1
Input
3 0 1 0
Output
1
Example 2
Input
4 0 2 1 0
Output
1
Hints
- On the way up a[i] < a[i + 1]; on the way down a[i] > a[i + 1].
- Binary search for the first index where a[mid] > a[mid + 1] — that is the peak.
Approach
The test a[mid] < a[mid + 1] is true on the rising slope and false from the peak onwards. If it's true, the peak is to the right (lo = mid + 1). Otherwise mid could be the peak (hi = mid). When lo meets hi, that's the peak.
Complexity: O(log n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &v : a) cin >> v;
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] < a[mid + 1]) lo = mid + 1;
else hi = mid;
}
cout << lo << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : data[0] + 1]
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < a[mid + 1]:
lo = mid + 1
else:
hi = mid
print(lo)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (a[mid] < a[mid + 1]) lo = mid + 1;
else hi = mid;
}
System.out.println(lo);
}
}