Peak of a Mountain Array
Problem
An array first goes strictly up and then strictly down (one of the two parts can be empty, so the biggest element can also be the first or the last one). All numbers are different. Print the index of the biggest element. Use binary search, so that your solution is O(log n).
Constraints
- 3 <= n <= 10^5
- strictly up, then strictly down
Examples
Input
5 1 3 5 4 2
Output
2
Solutions
Each step throws away half of the array, because the slope at the middle tells on which side the peak is. Linear search also works but takes O(n).
/*
* Problem : Find the peak.
* Input : n, then n integers.
* Output : The peak index.
* Approach: Binary search.
* Time : O(log n)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int solve(int[] a) {
// Step 1: The peak is always between low and high. Look at the middle element and its right neighbour.
int low = 0;
int high = a.length - 1;
while (low < high) {
int middle = low + (high - low) / 2;
// Step 2: If the next element is bigger, we are still going up, so the peak is to the right.
if (a[middle] < a[middle + 1]) {
low = middle + 1;
} else {
// Step 3: Otherwise the middle element can be the peak, so keep it and look to the left.
high = middle;
}
}
return low;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
System.out.println(solve(a));
}
}
Hints (1)
- How does the slope tell us where the peak is?