LeetCode 1095 Solutions

LeetCode 1095: Find in Mountain Array

/**
 * // 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 len = mountainArr.length();
        int l = 0, r = len - 1;
        int ml, mr, index;
        while(l <= r) {
            ml = l + (r - l) / 3;
            mr = r - (r - l) / 3;
            cout << l << " " << ml << " " << mr << " " << r << endl;
            if(mountainArr.get(ml) > mountainArr.get(mr)) {
                r = mr - 1;
            } else {
                l = ml + 1;
            }
        }
        index = ml;
        l = 0, r = index;
        int m;
        while(l <= r) {
            m = (l + r) / 2;
            int num = mountainArr.get(m);
            if(num == target) {
                return m;
            }
            if(num < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        l = index + 1, r = len - 1;
        while(l <= r) {
            m = (l + r) / 2;
            int num = mountainArr.get(m);
            if(num == target) {
                return m;
            }
            if(num < target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
};