Untitled

mail@pastecode.io avatar
unknown
plain_text
3 years ago
2.0 kB
4
Indexable
Never
/**
 * // 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 &mountainArr) {
        
        int start=0, last = mountainArr.length()-1, end = last, mid, peak;
        
        while(start<=last){
            mid = start + (last-start)/2;
            if(mountainArr.get(mid)>mountainArr.get(mid-1) 
               && mountainArr.get(mid)>mountainArr.get(mid+1)){peak=mid; break;}
            else if(mountainArr.get(mid)<mountainArr.get(mid+1)){start = mid+1;}
            else{last = mid-1;}
        }
        
        if(mountainArr.get(peak) == target){return peak;}
        
        int up = searchUp(target, 0, peak, mountainArr);
        int down = searchDown(target, peak+1, end, mountainArr);
        
        cout<<peak<<" "<<up<<" "<<down<<endl;
        
        if(up==-1 && down==-1){return -1;}
        else if(up==-1){return down;}
        else if(down==-1){return up;}
        else if(up>down){return down;}
        else{return up;}
        
    }
    
    int searchUp(int target, int start, int last, MountainArray &mountainArr){
            int mid;
            while(start<=last){
                mid = start + (last-start)/2;
                if(mountainArr.get(mid) == target){return mid;}
                else if(mountainArr.get(mid)<target){start = mid+1;}
                else{last = mid-1;}
            }
        return -1;
    }
    
    int searchDown(int target, int start, int last, MountainArray &mountainArr){
            int mid;
            while(start<=last){
                mid = start + (last-start)/2;
                if(mountainArr.get(mid) == target){return mid;}
                else if(mountainArr.get(mid)>target){start = mid+1;}
                else{last = mid-1;}
            }
        return -1;
    }
};