Find the minimum value of flipped array [Abstract bisection]

Preface

Abstract dichotomy , Common test questions , With the idea of binary fast approximation , Abstract judgment rules , Realize low time complexity search target.

One 、 Find the minimum value of the flipped array

Two 、 Abstract dichotomy + Equal treatment details of the first, middle and last three

package everyday.medium;

public class FindMin {
    
    /* target： Find the minimum , Direct Abstract dichotomy , But notice before   in   When the last three are equal . [2,2,2,2,2,2,2,0,1,2] | [2,2,2,0,1,2,2,2,2,2,2]  broken ？ When left, middle and right are equal , Then there is no hurry to take mid, Instead, go one space to the left on the right , So the value on the left is less than or equal to nums[high] Of .  Finally get the tail of the first array  i, be i+1 Even if the minimum value is . */
    public int findMin(int[] nums) {
    
        //  Bisection search k, 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
            int midVal = nums[mid];

            if (midVal > first) low = mid;
            else if (midVal < first) high = mid - 1;
            else if (midVal == nums[high]) high--;// Take a step to the left , Walking edge is a smaller value 
                //  Can merge .
            else low = mid;
        }
        return low + 1 == nums.length ? nums[0] : nums[low + 1];
    }
}

summary

1） Abstract dichotomy exercise , Rounding details of dichotomy + low/high No carry details .

reference

[1] LeetCode Find the minimum value of the flipped array