Give you an array numbers that may have duplicate element values. It was originally an array arranged in ascending order, and it was rotated once according to the above situation. Please return the sm

Post the code first ：

class Solution {
    public int minArray(int[] numbers) {
        int left = 0; //  Define the left pointer 
        int right = numbers.length-1; //  Define the right pointer 
        if (right == 0){
            return numbers[0];
        }
        while (left < right){
            int mid = left + (right - left) / 2; //  Define intermediate pointer 
            if (numbers[mid] > numbers[right]){ //  If the middle value is greater than the rightmost value , It indicates that the dividing point is mid On the right 
                left = mid + 1;
            }else if (numbers[mid] < numbers[right]){ //  If the middle value is less than the rightmost , Then the dividing point is mid On the left 
                right = mid;
            }else if (numbers[mid] == numbers[right]){ //  If the middle value is equal to the left and right , Then the violence narrows 
                right--;
            }
        }
        return numbers[left];
    }
}

Their thinking ：

         The title gives us a rotated , And there may be an array of duplicate elements numbers , It is required to find the minimum value of this array .

        If you don't consider the particularity of this array , Just find the minimum value in the array , I believe everyone knows to traverse the array first , Compare the previous element with the latter , Until the minimum value is found after traversing the array . Or sort the array first , Directly output the first element of the array .

         These are some elementary ways of writing , If the questions are these , Then you won't get the array with repeated elements after the rotation at all . So if you want to solve problems efficiently , We must start with this special array . So let's take a look at , What is passing once “ rotate ” Array after .

        “ Move the elements at the beginning of an array to the end of the array ”, This practice is called array “ rotate ”. For example, an array of 【1,2,3,4,5】 After rotation, it becomes 【4,5,1,2,3】：

         From the question , Before the array starts to rotate, it is an ascending array , Then we can come to the conclusion that , An array is rotated once , It is composed of two ascending arrays . in other words , This new array , It is composed of two ascending arrays .

        So at this point , You can use binary search , To find the minimum value of this new array . Now there is a question , Isn't binary search applicable to an ordered array ？ These two ordered arrays are combined , Does it apply ？

        Let's see , Whether dichotomy is suitable for the situation just now . It can be seen from the above figure , The rotated array is moved from the front elements to the back , So the smallest element must be the first element of the next ordered array , That is, where the next ordered array and the previous ordered array want to contact , It is called the dividing point ！ So corresponding , Once we find the dividing point , The minimum value is found . So how to find the dividing point ？

         Let's first set the left and right boundaries of the array left and right , And find the middle position , Set to mid , Then there is ：

        When mid Less than right when , Explain what ？ Description from mid Start Back until right , Is an ordered array in ascending order , Then the dividing point may be mid On the right ？ impossible ！ So I want to find the dividing point , Only in mid To the right . Then the above array becomes ：

         Now let's judge , When mid dayu right when , What does this mean ？ Description from mid Start To right , There is a fault in the middle , Then this fault is the dividing point we are looking for ！ So let the left boundary left Turn into mid + 1 .

         When left and right When both point to the same value , It means that the dividing point has been found , Then it means that the minimum value of the array is found . At this time, let's go back and analyze , We just solved the problem , Is the method of finding the dividing point the binary search method ？

        But in the above process, we have neglected a problem , The title indicates that there may be duplicate elements in the array , So when repeated elements appear , Does the above analysis still work ？ Obviously, it doesn't work anymore ！ Because when mid and right and left When the values of are equal , It is impossible to judge whether it is  mid Is the left side an ordered array or mid On the right It's an ordered array . What should I do at this time ？ As shown in the figure below ：

        Now? mid、left、right It's all the same value , It's impossible to judge who is orderly , Now we can only narrow the scope manually , take right Move one bit to the right , namely right -- ！ such , It becomes ：

         At this time, we can judge ！