---
# System prepended metadata

title: LeetCode 852. Peak Index in a Mountain Array
tags: [Leetcode]

---

# LeetCode 852. Peak Index in a Mountain Array
[LeetCode 852. Peak Index in a Mountain Array]([leetcode_url](https://leetcode.com/problems/peak-index-in-a-mountain-array/description/)) (<font color=#FFB800>Medium</font> 68.5%)

<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :
> 3 <= arr.length <= $10^5$
> 0 <= arr[i] <= $10^6$
> `arr` is guaranteed to be a mountain array.



- Solution
    也是 binary tree，沒什麼特別的。
    - 時間複雜度: $O(lgn)$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        int peakIndexInMountainArray(vector<int>& arr) {
            if(arr[0]> arr[1]) return 0;
            if(arr[arr.size() - 2 ]< arr[arr.size() - 1]) return arr.size() - 1;

            int left_index = 0, r_index = arr.size() - 1, mid_index;
            while(left_index <= r_index)
            {
                mid_index = (r_index - left_index) / 2 + left_index;
                if(arr[mid_index] > arr[mid_index + 1] && arr[mid_index] > arr[mid_index - 1]) return mid_index;
                else if(arr[mid_index] < arr[mid_index + 1]) left_index = mid_index + 1;
                else if(arr[mid_index] < arr[mid_index - 1]) r_index = mid_index - 1;
            }
            return -1;
        }
    };
    ```
</details>