package leetcode;

/**
 * https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
 */
public class Problem154 {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    }

    private int findMin(int[] nums, int left, int right) {
        if (left >= right) {
            return nums[left];
        }
        int mid = (left + right) / 2;
        int minLeft = nums[left];
        if (mid - 1 >= 0) {
            minLeft = Math.min(minLeft, nums[mid - 1]);
        }
        int minRight = nums[right];
        if (mid + 1 < nums.length) {
            minRight = Math.min(minRight, nums[mid + 1]);
        }
        int min = Math.min(minLeft, Math.min(nums[mid], minRight));
        if (min == nums[mid]) {
            if (minLeft < minRight) {
                return findMin(nums, left, right - 1);
            } else {
                return findMin(nums, left + 1, right);
            }
        }
        if (minLeft < minRight) {
            return findMin(nums, left, mid - 1);
        } else {
            return findMin(nums, mid + 1, right);
        }
    }

    private static String debug(int[] nums, int left, int right) {
        StringBuilder sb = new StringBuilder();
        for (int i = left; i <= right; i++) {
            sb.append(nums[i] + " ");
        }
        return sb.toString();
    }
}

@@ -1112,253 +1112,7 @@
    %7D
-%0A%0A    private static String debug(int%5B%5D nums, int left, int right) %7B%0A        StringBuilder sb = new StringBuilder();%0A        for (int i = left; i %3C= right; i++) %7B%0A            sb.append(nums%5Bi%5D + %22 %22);%0A        %7D%0A        return sb.toString();%0A    %7D
 %0A%7D%0A

Update problem 154