1095 find in mountain array

https://leetcode.com/problems/find-in-mountain-array/

/**
 * // 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) {
        Map<Integer, Integer> cache = new HashMap<>();
        int peak = findPeak(mountainArr, cache);
        int left = findInLeft(mountainArr, peak, target, cache);
        if (left == -1) {
            return findInRight(mountainArr, peak, target, cache);
        }
        return left;
    }
    private int findPeak(MountainArray mountainArr, Map<Integer, Integer> cache) {
        int len = mountainArr.length();
        int left = 0;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int midVal = getFromCache(cache, mid, mountainArr);
            int leftVal = getFromCache(cache, left, mountainArr);
            int rightVal = getFromCache(cache, right, mountainArr);
            if (leftVal < midVal && midVal < rightVal) {
                left = mid;
            } else if (leftVal > midVal && midVal > rightVal) {
                right = mid;
            } else {
                left = mid;
            }
        }
        int leftVal = mountainArr.get(left);
        int rightVal = mountainArr.get(right);
        if (leftVal > rightVal) {
            return left;
        }
        return right;
    }
    private int findInLeft(MountainArray arr, int peak, int target, Map<Integer, Integer> cache) {
        int left = 0;
        int right = peak;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int midVal = getFromCache(cache, mid, arr);
            int leftVal = getFromCache(cache, left, arr);
            int rightVal = getFromCache(cache, right, arr);
            
            if (midVal == target) {
                return mid;
            } 
            if (midVal < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        int leftVal = arr.get(left);
        int rightVal = arr.get(right);
        if (leftVal == target) {
            return left;
        } else if (rightVal == target) {
            return right;
        }
        return -1;
    }
    private int findInRight(MountainArray arr, int peak, int target, Map<Integer, Integer> cache) {
        int left = peak + 1;
        int right = arr.length() - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int midVal = getFromCache(cache, mid, arr);
            int leftVal = getFromCache(cache, left, arr);
            int rightVal = getFromCache(cache, right, arr);
            
            if (midVal == target) {
                return mid;
            } 
            if (midVal < target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        int leftVal = arr.get(left);
        int rightVal = arr.get(right);
        if (leftVal == target) {
            return left;
        } else if (rightVal == target) {
            return right;
        }
        return -1;
    }
    private int getFromCache(Map<Integer, Integer> cache, int idx, MountainArray arr) {
        int val;
        if (!cache.containsKey(idx)) {
            val = arr.get(idx);
            cache.put(idx, val);
        } else {
            val = cache.get(idx);
        }
        return val;
    }
}

find peak应该有更好的办法，这里用cache有点取巧了感觉，总体思路是find peak之后在peak两边分别做二分查找，注意如果左右都有要返回左边的

private int findPeak(MountainArray mountainArr) {
        int len = mountainArr.length();
        int left = 0;
        int right = len - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            int midVal = mountainArr.get(mid);
            int midLeftVal = mountainArr.get(mid + 1);
            
            if (midVal < midLeftVal) {
                left = mid;
            } else {
                right = mid;
            }
        }
        int leftVal = mountainArr.get(left);
        int rightVal = mountainArr.get(right);
        if (leftVal > rightVal) {
            return left;
        }
        return right;
    }

逻辑更清楚的findPeak，比较mid和mid+1的趋势，但是这个还是得用cache，不过好像大家都在用cache