Poison

852. Peak Index in a Mountain Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int i = 0, j = arr.length - 2; // [i, j]
int peakIndex = 0;
while (i <= j) {
int mid = (i + j) >>> 1;
if (arr[mid] < arr[mid + 1]) {
i = mid + 1;
} else {
peakIndex = mid;
j = mid - 1;
}
}

return peakIndex;
}
}
Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int peakIndexInMountainArray(int[] arr) {
// 山脉数组的特点:前半部分递增,后半部分递减,我们每次判断中点位于前半部分还是后半部分即可
int left = 0, right = arr.length - 1;
while (left < right) {
int mid = (left + right) >>> 1;
if (arr[mid] < arr[mid + 1]) {
// 当前中点在前半部分
left = mid + 1;
} else {
// 当前中点在后半部分
right = mid;
}
}

return left;
}
}
Reference

852. Peak Index in a Mountain Array
剑指 Offer II 069. 山峰数组的顶部