1095

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    int findInMountainArray(int target, MountainArray &arr) {
        int n = arr.length();
        int l=0, r=n-1;

        // Find peak.
        while(l<r){
            int mid = (l+r)/2;
            if(arr.get(mid) < arr.get(mid+1))
                l = mid+1;
            else
                r = mid;
        }
        int k = l;

        // Search left space.
        l=0; r=k;
        while(l<=r){
            int mid = (l+r)/2;
            int val = arr.get(mid);
            if(val == target)
                return mid;
            else if(val < target)
                l = mid+1;
            else
                r = mid-1;
        }

        // Search right space.
        l = k+1, r = n-1;
        while(l<=r){
            int mid = (l+r)/2;
            int val = arr.get(mid);
            if(val == target)
                return mid;
            else if(val < target)
                r = mid-1;
            else
                l = mid+1;
        }
        return -1;
    }

};