## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Find peak in array

Sharing is caring!

Problem statement
A peak element is an element that is greater than its neighbors. Given an input array where $num[i] \ne num[i+1]$, find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that $num[-1] = num[n] = -\infty$.

For example: in array $[1, 2, 3, 0, 4, 5, 2, 1, 4, 2]$, $3$ is a peak element and your function should return the index number $2$.

Solution
We approach this problem using binary search to achieve an $\mathcal{O}(\log n)$ running time.

The key to solving this problem is:
1. If $num[mid] \textless num[mid - 1]$ then a peak element exist to the left of $mid$.
2. If $num[mid] \textless num[mid + 1]$ then a peak element exist to the right of $mid$.

Proof of 1.:
Since $num[mid - 1] \textgreater num[mid]$, $num[mid - 1]$ is already a peak candidate.

• If no $num[mid - 2]$ exists, then $num[mid - 1]$ is our peak.
• If $num[mid - 2]$ exists and $num[mid - 2] \textless num[mid - 1]$, then $num[mid - 1]$ is our peak.
• If $num[mid - 2]$ exists but $num[mid - 2] \textgreater num[mid - 1]$ then: while $num[mid - i] \textgreater latex num[mid - i + 1]$ keep going left until you reach the border (in which case the first element will be a peak) or until you find an element $num[mid - i] \textless num[mid - i + 1]$ in which case $num[mid - i + 1]$ will be our peak.

Full code

public class FindPeak {
private static int findPeak(int[] array, int start, int end) {
int mid = (start + end) / 2;

if ((mid > 0 && mid < end) && (array[mid] > array[mid - 1] && array[mid] > array[mid + 1])) {
return mid;
} else if (mid == 0 && array[mid] > array[mid + 1]) {
return mid;
} else if (mid == end && array[mid] > array[mid - 1]) {
return mid;
}

if (array[mid] < array[mid - 1]) {
// A peak exists to the left
return findPeak(array, start, mid - 1);
}

if (array[mid] < array[mid + 1]) {
// A peak exists to the right
return findPeak(array, mid + 1, end);
}

return 0;
}

public static void main(String[] args) {
int[] array = { 1, 2, 3, 0, 4, 5, 2, 1, 4, 2 };
System.out.println(findPeak(array, 0, array.length - 1));
}
}