Leetcode 852. Peak Index in a Mountain Array Binary Search

Let’s call 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 an integer array arr that is guaranteed to be a mountain, return any i such that arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

Follow up: Finding the O(n) is straightforward, could you find an O(log(n)) solution?

給一個陣列arr，長度必定 >= 3，且必定為山形，也就是有一個波頂

遍尋可以找出最大值，但題目要求要O(log n)。考慮到山也有順序性(從高到低，從低到高)，故使用Binary search

解題步驟

1. 定義left, right
2. while直到right小於等於left
3. 找出中間點mid，假設mid>左右兩邊，則為峰頂
4. 假設右邊比mid高，則left 設為 mid + 1
5. 假設左邊比mid高，則right設為mid – 1

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function(arr) {
    let left = 0;
    let right = arr.length - 1;
    while(left <= right){
        let mid = Math.round((left + right)/2)
        if(arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]){
            return mid;
        }else if(arr[mid] >= arr[mid-1]){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
};