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]) {
            return nums[mid];
        }
        if (minLeft < minRight) {
            return findMin(nums, left, mid - 1);
        } else {
            return findMin(nums, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        Problem154 prob = new Problem154();
        System.out.println(prob.findMin(new int[]{4, 5, 6, 7, 0, 1, 2})); // 0
//        System.out.println(prob.findMin(new int[]{4, 4, 5, 6, 7, 0, 1, 2, 2})); // 0
//        System.out.println(prob.findMin(new int[]{4, 4, 5, 6, 7, 2, 2, 3})); // 2
//        System.out.println(prob.findMin(new int[]{3, 3, 3, 3, 3, 3, 3, 3, 1, 3})); // 1
    }
}

@@ -766,25 +766,178 @@
     
-return nums%5Bmid%5D;
+if (minLeft %3C minRight) %7B%0A                return findMin(nums, left, right - 1);%0A            %7D else %7B%0A                return findMin(nums, left + 1, right);%0A            %7D
 %0A   
@@ -1119,21 +1119,22 @@
    p
-ublic
+rivate
  static 
 void
@@ -1133,418 +1133,227 @@
 tic 
-void main(String%5B%5D args) %7B%0A        Problem154 prob = new Problem154();%0A        System.out.println(prob.findMin(new int%5B%5D%7B4, 5, 6, 7, 0, 1, 2%7D)); // 0%0A//        System.out.println(prob.findMin(new int%5B%5D%7B4, 4, 5, 6, 7, 0, 1, 2, 2%7D)); // 0%0A//        System.out.println(prob.findMin(new int%5B%5D%7B4, 4, 5, 6, 7, 2, 2, 3%7D)); // 2%0A//        System.out.println(prob.findMin(new int%5B%5D%7B3, 3, 3, 3, 3, 3, 3, 3, 1, 3%7D)); // 1
+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   

Solve problem 154