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;
    }
}

References

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