# Leetcode 852. Peak index in a mountain array

## 題目

An array arr a mountain if the following properties hold:

arr.length >= 3
There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

 

Example 1:

Input: arr = [0,1,0]
Output: 1
Example 2:

Input: arr = [0,2,1,0]
Output: 1
Example 3:

Input: arr = [0,10,5,2]
Output: 1
 

Constraints:

3 <= arr.length <= 105
0 <= arr[i] <= 106
arr is guaranteed to be a mountain array.

## 概述
題目要求從給定的陣列內找出最大值，並且返回所在位置的下標，而題目想定這是一座山峰，且有特別要求時間複雜度必須要到 O(logn)，所以馬上就聯想到了二分查找，但是二分查找是需要給定目標值才能做分割查找，這一題的測資沒有給定目標值，那要怎麼找呢？

這題有說到 arr[i] 左右邊的值都會小於它 (注意題目第4行)，所以我們使用二分查找的時候，只要確定兩個條件即可，即：

**arr[mid] > arr[mid + 1]** or **arr[mid] < arr[mid + 1]**

並且題目還有說到，3 <= arr.length <= 105，由此可知，題目給定的起始山峰陣列必定是 **小大小** 的組合排列，所以我們不需要處理 **空陣列** 或是 **小於3** 的 corner case，並且我們的起始下標 left 可以從 1 開始，而 right 可以從 arr.size() - 2 開始。

## 代碼

既然條件確立，起始上下界也確立了，接下來就套用到二分查找即可：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1;
        int right = arr.size() - 2;
        int ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            }
            else {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }
}

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right = 1, n - 2
        ans = 0
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] < arr[mid + 1]:
                left = mid + 1
            else:
                ans = mid
                right = mid - 1
        return ans