1095. Find in Mountain Array

• Array를 100번 이상 접근할 수 없다는 제약이 걸려있는 경우 지정된 숫자의 index를 효율적으로 찾는 방법을 구현한다.
• 사실 array 접근 횟수에 제한이 없다면 처음부터 훑어서 target을 찾아내도 되겠지만…

• 먼저 mountain array의 max index를 찾는다 findMax.
• max index를 찾는데에도 binary search를 적용할 수 있다.
• 현재 범위 (start, end)를 기준으로 중간 index pivot을 정한다.
• pivot을 기준으로 앞 before, 현재 current, 뒤 after 의 값을 구한 뒤 비교한다.
• 세 값 중 current 값이 제일 큰 값이라면 pivot이 max index가 된다.
• 값이 증가하는 형태라면 max index는 pivot 오른쪽에 위치할 것이다. 왜냐하면 pivot 위치는 산의 왼쪽 사분면이기 때문이다.
• 값이 감소하는 형태라면 max index는 pivot 왼쪽에 위치할 것이다. 왜냐하면 pivot 위치는 산의 오른쪽 사분면이기 때문이다.

• Max index를 기준으로 왼쪽, 오른쪽에 각각 binary search를 적용한다 findTarget.
• 단순히 binary search를 적용하는 것인데 왼쪽 범위를 먼저 찾고 없으면 오른쪽을 찾는다.
• 오른쪽 범위를 찾을때는 값이 내림차순 정렬되어있음에 주의한다.

class Solution {
public:
    int findMax(MountainArray &m, int start, int end) {
        while (start < end) {
            int pivot = (end - start) / 2 + start;
            int before = pivot > 0? m.get(pivot - 1) : INT_MIN;
            int current = m.get(pivot);
            int after = pivot < end - 1? m.get(pivot + 1) : INT_MAX;
            if (before < current && current > after) {
                // max
                return pivot;
            } else if (before < current && current < after) {
                // increasing
                start = pivot + 1;
            } else {
                // descreasing
                end = pivot;
            }
        }
        return start;
    }

    int findTarget(MountainArray &m, int start, int end, int target, bool left) {
        while (start < end) {
            int pivot = (end - start) / 2 + start;
            int current = m.get(pivot);
            if (current == target) return pivot;
            else if ((target < current) == left) {
                end = pivot;
            } else {
                start = pivot + 1;
            }
        }
        return -1;
    }
    
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int N = mountainArr.length();
        int pivot = findMax(mountainArr, 0, N);
        int left = findTarget(mountainArr, 0, pivot, target, true);
        if (left != -1) return left;
        return findTarget(mountainArr, pivot, N, target, false);
    }
};