Leetcode 1095. Find in Mountain Array

アプローチ

Binary Search

説明

• 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) {
        // find top index
        int topIndex = 0;
        int left = 0;
        int right = mountainArr.length() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
                topIndex = mid + 1;
            } else {
                right = mid;
            }
        }

        // check left of top index
        left = 0;
        right = topIndex;

        while (left <= right) {
            int mid = (left + right) / 2;
            int value = mountainArr.get(mid);
            if (value < target){
                left = mid + 1;
            } else if (value > target) {
                right = mid - 1;
            } else {
                return mid;
            }

        }

        // check right of  top index
        left = topIndex;
        right = mountainArr.length() - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int value = mountainArr.get(mid);
            if (value > target) {
                left = mid + 1;
            } else if (value < target) {
                right = mid - 1;
            } else {
                return mid;
            }

        }

        return -1;
    }
}

参考にした解説