[852. Peak Index in a Mountain Array](https://leetcode.com/problems/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` <= 10^5^
* 0 <= `arr[i]` <= 10^6^
* `arr` is **guaranteed** to be a mountain array.

### 解答

#### C++

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        return binarySearch(arr);
    }

    int binarySearch(vector<int>& arr) {
        int left = 0, right = arr.size();

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
            // printf("left=%d\tright=%d\tmid=%d\n", left, right, mid);
        }
        return left;
    }
};

[Step by Step 的講解](https://docs.google.com/presentation/d/1cGs_CqvYpXNwQk7gkGOLUJP5durAEviUsMld8OtzIBg/edit?usp=sharing)

> [name=Jerry Wu][time=25 July, 2023]

#### Javascript

function peakIndexInMountainArray(arr) {
  let min = 0;
  let max = arr.length - 1;

  while (max > min) {
    const mid = (min + max) >> 1;
    if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1]) return mid;
    if (arr[mid] > arr[mid - 1]) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }
}

> 幾個月沒做binary search的題目而已...又因為邊界條件錯了兩次...
> [name=Marsgoat][time=25 July, 2023]

function peakIndexInMountainArray(arr) {
  let min = 0;
  let max = arr.length - 1;

  while (max > min) {
    const mid = (min + max) >> 1;
    if (arr[mid] < arr[mid + 1]) {
      min = mid + 1;
    } else {
      max = mid;
    }
  }

  return min;
}

> 把`if (arr[mid] > arr[mid + 1] && arr[mid] > arr[mid - 1])`這段判斷拿掉了，多此一舉，最後return min就好了，不用每次都判斷反而慢
> [name=Marsgoat][time=25 July, 2023]

#### TypeScript

function peakIndexInMountainArray(arr: number[]): number {
  const binarySearch = (arr: number[], start: number, end: number): number => {
    if (start >= end - 1) {
      return arr[start] > arr[end] ? start : end;
    }

    const mid = (end + start) >> 1;
    const midEl = arr[mid];

    if (midEl > arr[mid - 1] && midEl > arr[mid + 1]) {
      return mid;
    } else if (midEl < arr[mid - 1]) {
      return binarySearch(arr, start, mid);
    } else {
      return binarySearch(arr, mid, end);
    }
  };

  return binarySearch(arr, 0, arr.length - 1);
}

> [name=Sheep][time=26 July, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)