/*
 * @lc app=leetcode id=852 lang=cpp
 *
 * [852] Peak Index in a Mountain Array
 */

// @lc code=start
class Solution {
public:
    void bsearch(int L, int R, vector<int>& arr, int& loc, int& mx){
        if(L+1 >= R){
            if(arr[L] > mx){
                mx = arr[L];
                loc = L;
            }
            return ;
        }
        int mid = (L+R)/2;
        if(arr[mid] > arr[R-1]){
            bsearch(L, mid+1, arr, loc, mx);
        }
        if(arr[mid] > arr[L]) {
            bsearch(mid, R, arr, loc, mx);
        }
    }
    int peakIndexInMountainArray(vector<int>& arr) {
        int N = arr.size();
        int loc = 0;
        int mx = 0;
        bsearch(0, N, arr, loc, mx);
        return loc;
    }
};
// @lc code=end