Untitled

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

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int peak = findPeak(mountainArr);

        int low = 0;
        int high = peak;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            int midValue = mountainArr.get(mid);

            if (midValue == target) {
                return mid;
            }

            if (midValue > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        low = peak + 1;
        high = mountainArr.length() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            int midValue = mountainArr.get(mid);

            if (midValue == target) {
                return mid;
            }

            if (midValue > target) {
                low = low + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;
    }

    private int findPeak(MountainArray mountainArr) {
        int low = 1;
        int high = mountainArr.length() - 2;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            int midValue = mountainArr.get(mid);
            int prevValue = mid - 1 == -1 ? Integer.MIN_VALUE : mountainArr.get(mid - 1);
            int nextValue = mid + 1 == mountainArr.length() ? Integer.MIN_VALUE : mountainArr.get(mid + 1);

            if (midValue > prevValue && midValue > nextValue) { // peak
                return mid;
            }

            if (midValue > prevValue) { // increasing side
                low = mid + 1;
            } else { // decreasing
                high = mid - 1;
            }
        }

        return -1;
    }
}