-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPeakElement.java
More file actions
54 lines (45 loc) · 1.43 KB
/
Copy pathPeakElement.java
File metadata and controls
54 lines (45 loc) · 1.43 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package array;
/**
* A peak element is an element that is greater than its neighbors.
*
* Given an input array where num[i] ≠ 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] = -∞.
*
* For example, in array [1, 2, 3, 1], 3 is a peak element and your function
* should return the index number 2.
*
* https://leetcode.com/problems/find-peak-element/description/
*
* @author Surajeet Sen
*/
public class PeakElement {
public static void main(String[] args) {
int [] nums = {1, 2, 3, 1};
System.out.println(new PeakElement().findPeakElement(nums));
}
public int findPeakElement(int[] nums) {
return findPeakRec(nums, 0, nums.length-1);
}
private int findPeakRec(int[] arr, int low, int high) {
if(low == high) {
return low;
}
if(high - low == 1) {
return (arr[high] > arr[low]) ? high : low;
}
int mid = low + (high-low)/2;
if(arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]) {
return mid;
}
if(arr[mid] < arr[mid+1]) {
return findPeakRec(arr, mid+1, high);
} else {
return findPeakRec(arr, low, mid-1);
}
}
}