面试算法69：山峰数组的顶部

题目

在一个长度大于或等于3的数组中，任意相邻的两个数字都不相等。该数组的前若干数字是递增的，之后的数字是递减的，因此它的值看起来像一座山峰。请找出山峰顶部，即数组中最大值的位置。例如，在数组[1，3，5，4，2]中，最大值是5，输出它在数组中的下标2。

分析

可以根据山峰数组的这个特点应用二分查找算法。先取出位于数组中间的数字。如果这个数字比它前后两个数字都大，那么就找到了数组的最大值。如果这个数字比它前一个数字大但比后一个数字小，那么这个数字位于数组递增的部分，数组的最大值一定在它的后面，接下来只需要在数组的后半部分查找就可以。如果这个数字比它前一个数字小但比后一个数字大，那么这个数字位于数组递减的部分，数组的最大值一定在它的前面，接下来只需要在数组的前半部分查找就可以。

解

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 4, 2};
        System.out.println(peakIndexInMountainArray(nums));
    }

    public static int peakIndexInMountainArray(int[] nums) {
        int left = 1;
        int right = nums.length - 2;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }

            if (nums[mid] > nums[mid - 1]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return -1;
    }
}