# Find peak in array

**Problem statement**

A peak element is an element that is greater than its neighbors. Given an input array where , 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 .

For example: in array , is a peak element and your function should return the index number .

**Solution**

We approach this problem using binary search to achieve an running time.

The key to solving this problem is:

1. If then a peak element exist to the left of .

2. If then a peak element exist to the right of .

Proof of 1.:

Since , is already a peak candidate.

- If no exists, then is our peak.
- If exists and , then is our peak.
- If exists but then: while keep going left until you reach the border (in which case the first element will be a peak) or until you find an element in which case 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)); } }