package buildingblock.searching.lc154_findminimuminrotatedsortedarray2;

/**
 * Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?
 * Would this affect the run-time complexity? How and why?
 */
public class Solution {

    // Where problems arise:
    //  [2,3,4,4,4] => min=4, since nums[2](4) < nums[4](4) is false, continue to search in [2,4]
    //  [4,4,4,1,4] => min=4, since nums[2](4) <= nums[4](4) is true, continue to search in [0,2]
    // Then how can we know if left or right half is rotated or not?
    // So you know nothing if nums[low] = nums[mid] = nums[high], both half is required to search.
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    }

    private int findMin(int[] nums, int low, int high) {
        if (low == high) {
            return nums[low];
        }

        int mid = (low + high) / 2;

        // Right half is ordered, continue search on [low,mid]
        if (nums[mid] < nums[high]) {
            return findMin(nums, low, mid);
        }

        // Right half is disordered, continue search on [mid + 1,high]
        if (nums[mid] > nums[high]) {
            return findMin(nums, mid + 1, high);
        }

        // Uncertain, search both sides. eg.[4,2,4,4,4] or [4,4,4,2,4]
        return Math.min(findMin(nums, low, mid), findMin(nums, mid + 1, high));
    }

}

@@ -247,16 +247,1609 @@
 tion %7B%0A%0A
+    // Inspired from leetcode discuss: O(N) in the worst case%0A    // But this approach will not return the correct index, only value%0A    public int findMin(int%5B%5D nums) %7B%0A        // Min element must be %5B0, n-1%5D%0A        int low = 0, high = nums.length - 1;%0A%0A        // MustBe(low,high)%0A        while (low %3C high) %7B%0A            int mid = low + (high - low) / 2;%0A            if (nums%5Bmid%5D %3E nums%5Bhigh%5D) %7B           // %5Bmid,high%5D is disordered%0A                low = mid + 1;%0A            %7D else if (nums%5Bmid%5D %3C nums%5Bhigh%5D) %7B    // %5Bmid,high%5D is in order%0A                high = mid;%0A            %7D else %7B                                // nums%5Bmid%5D=nums%5Bhigh%5D%0A                high--;                             // key: why it's safe to shrink from high bound...%0A            %7D                                       // because nums%5Bhigh%5D is impossible to be the only min (otherwise, nums%5Bmid%5D%3Enums%5Bhigh%5D)%0A        %7D%0A        return nums%5Blow%5D;%0A    %7D%0A%0A    // My 2nd: O(NlogN) in the worst case%0A    public int findMin2(int%5B%5D nums) %7B%0A        return doFindMin(nums, 0, nums.length - 1);%0A    %7D%0A%0A    private int doFindMin(int%5B%5D nums, int low, int high) %7B%0A        if (low %3E= high) %7B%0A            return nums%5Blow%5D;%0A        %7D%0A%0A        int mid = low + (high - low) / 2;%0A        if (nums%5Bmid%5D %3E nums%5Bhigh%5D) %7B%0A            return doFindMin(nums, mid + 1, high);%0A        %7D%0A        if (nums%5Bmid%5D %3C nums%5Blow%5D) %7B%0A            return doFindMin(nums, low, mid);%0A        %7D%0A        //return Math.min(doFindMin(nums, low, mid), doFindMin(nums, mid + 1, high));%0A        return doFindMin(nums, low, high - 1);%0A    %7D%0A%0A    // My 1st%0A
     // W
@@ -2247,32 +2247,33 @@
 blic int findMin
+1
 (int%5B%5D nums) %7B%0A 
@@ -2289,24 +2289,25 @@
 turn findMin
+1
 (nums, 0, nu
@@ -2344,32 +2344,33 @@
 vate int findMin
+1
 (int%5B%5D nums, int
@@ -2615,24 +2615,25 @@
 turn findMin
+1
 (nums, low, 
@@ -2776,32 +2776,33 @@
   return findMin
+1
 (nums, mid + 1, 
@@ -2917,24 +2917,25 @@
 .min(findMin
+1
 (nums, low, 
@@ -2943,24 +2943,25 @@
 id), findMin
+1
 (nums, mid +

leetcode-154 find minimum in rotated sorted array 2