山脉数组的峰顶索引

力扣 852. 山脉数组的峰顶索引

题目说明

符合下列属性的数组 arr 称为 山脉数组 ：
- arr.length >= 3
- 存在
  
  i（0 < i < arr.length - 1）使得：
  - arr[0] < arr[1] < ... arr[i-1] < arr[i]
- arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

示例

示例 1：

1 2	输入：arr = [0,1,0] 输出：1

示例 2：

1 2	输入：arr = [0,2,1,0] 输出：1

示例 3：

1 2	输入：arr = [0,10,5,2] 输出：1

示例 4：

1 2	输入：arr = [3,4,5,1] 输出：2

示例 5：

1 2	输入：arr = [24,69,100,99,79,78,67,36,26,19] 输出：2

笔者理解

此题是一道二分查找算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题是比较经典的二分查找，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 二分查找
     */
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;

        if (arr[left] > arr[left + 1]) {
            return left;
        }
        if (arr[right] > arr[right - 1]) {
            return right;
        }

        int mid;

        while (left < right) {
            mid = left + (right - left) / 2 + 1;

            // 条件根据题目数据设定，不具有普适性
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            else if(arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return left;
    }
}