1095. Find in Mountain Array.md

1095. Find in Mountain Array

• 本质是是道查找题
• 题目要求简化算法，利用O(lgN)的二分查找，数组也很特殊，像山一样。 引文这个特性，我们把数组分成两部分， 已山峰为分界点。找左面的符合要求的值，不然就找右面
• 难点是如何在山峰数组找到最高， 利用二分去比较 arr[mid] and arr[mid+1],然后决定去哪部分【这里的就像f(n)函数，在我的二分模板里】，
• 不过不同的是l =0, r=len-1 [l,r] -> while(l<r) break, this make sure mid+1 will not overflow

/**
 * // 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) {
        //find the top and it always exists
        //search in left increading array
        //search in right increasing array
        int topIndex = findTop(mountainArr);
        if(target > mountainArr.get(topIndex)) return -1;
        if(target == mountainArr.get(topIndex)) return topIndex;
        //[)
        int leftIndex = findLeft(target, mountainArr, 0, topIndex);
        if(leftIndex>=0 && leftIndex<topIndex) return leftIndex;
        int rightIndex = findRight(target, mountainArr, topIndex, mountainArr.length());
        if(rightIndex>topIndex && rightIndex<mountainArr.length()) return rightIndex;
        return -1;
    }
    int findRight(int target,MountainArray mountainArr, int l, int r){
        while(l<r){
            int mid = (r-l)/2+l;
            if(mountainArr.get(mid)==target) return mid;
            else if(mountainArr.get(mid)>target) {
                l = mid+1;
            }else{
                r = mid;
            }
        }
        return -1;
    }
    
    //[)
    int findLeft(int target,MountainArray mountainArr, int l, int r){
        while(l<r){
            int mid = (r-l)/2+l;
            if(mountainArr.get(mid)==target) return mid;
            else if(mountainArr.get(mid)<target) {
                l = mid+1;
            }else{
                r = mid;
            }
        }
        return -1;
    }
    //assume we must find the top index
    //how we find top index with such moutain array
    int findTop(MountainArray mountainArr){
        int l = 0, r = mountainArr.length()-1; 
        //[]
        while(l<r){
            int mid = (r-l)/2+l;
            //check mid+1 in the length
            if(mountainArr.get(mid)<mountainArr.get(mid+1)){
                l = mid+1;
            }else{
                r = mid;
            }
        }
        return l;  
    }
    
}