Find the minimum value in the rotation sort array ii[classical Abstract dichotomy + how to break the game left, middle and right are equal]

Preface

This question is a very classic Abstract dichotomy that I have done , Not only are decision rules abstract , And there will be decision rules “ Malfunction ” The phenomenon .
How to break the situation ？ And mining the characteristics of a given array , Use your personality , For those routes （ positive / Converse thinking ）, Break the problem , This is logic , Every cause has its effect , Use its cause to get its result , Not by chance .

One 、 Look for the minimum value in the rotation sort array II

Two 、 Classical Abstract dichotomy

package everyday.medium;

public class FindMin {
    
    /* target： Find the minimum , Direct Abstract dichotomy , But notice before   in   When the last three are equal .  Divide the rotated and non rotated subarrays into two subarrays .  How to abstract ？ Give Way nums[mid]  and  nums[0]  Compare , If more than nums[0]  be mid Must be in the first subarray ; If it is less than nums[0], that mid It must be in the second subarray .  A special case ： When nums[mid] = nums[0] when , Then look at nums[mid]  and  nums[high] The relationship between , if   If you don't wait, you must nums[mid] > nums[high], that mid It must be in the first subarray .  If so nums[mid]  Also equal to  nums[high] Na ？ as follows , [2,2,2,2,2,2,2,0,1,2] | [2,2,2,0,1,2,2,2,2,2,2]  How to break the situation ？ Notice the personality of these two subarrays , It's all incremental ; The maximum and minimum values are next to each other , And the only logarithm , They are not incremental .  When left, middle and right are equal , Then there is no hurry to take mid, can low Take a step forward , Break this three equal situation .  if low Bit is the largest bit ？ You can't low++!  see nums[low]  Is it greater than nums[low + 1], if ,nums[low] Must be the maximum value of the array , The minimum value follows immediately , Go straight back to .  Why not? high-- To break the situation ？ Because if high It is already in the maximum position ,high It can't move . Why not be like low  and  low + 1 To judge , Because both subarrays are incremented . The only non increasing pair can only be met from the front . */
    public int findMin(int[] nums) {
    
        //  Find the maximum value in two , The minimum value will follow immediately , Abstract dichotomy .
        int low = 0, high = nums.length - 1;
        //  Two points can be found quickly nums[0] Small , The first small one .
        int first = nums[0];
        while (low < high) {
    
            int mid = low + (high - low + 1 >>> 1);// here +1 Very important , It needs to be rectified , With the following low = mid Prevent a dead cycle .
            int midVal = nums[mid];

            if (midVal > first) low = mid;
            else if (midVal < first) high = mid - 1;
                //  The key to breaking the game .
            else if (midVal == nums[high]) {
    
                //  Three important cases 
                // [3,3,1,3] [3,1,3,3] [2,2,2,0,2,2]
                if (nums[low] <= nums[low + 1]) low++;
                    //  The maximum and minimum values are next to each other , And the only logarithm , They are not incremental .
                else return nums[low + 1];
            }
            //  Can merge .
            else low = mid;
        }
        return high + 1 == nums.length ? nums[0] : nums[high + 1];
    }
}

summary

1） Classic Abstract dichotomy exercise .
2） Use its cause ( Title Display | Implicit ( Careful excavation is required ) Conditions / Personality characteristics ), Must have its fruit , Not by chance , This is logic .

reference

[1] LeetCode Look for the minimum value in the rotation sort array II