Sword finger offer 11 Minimum number of rotation array - binary lookup

One 、 Title Description

Move the first elements of an array to the end of the array , We call it rotation of arrays .

Give you a chance to exist repeat An array of element values numbers , It turns out to be an ascending array , And a rotation is carried out according to the above situation . Please return the smallest element of the rotation array . for example , Array [3,4,5,1,2] by [1,2,3,4,5] A rotation of , The minimum value of the array is 1.

Be careful , Array [a[0], a[1], a[2], …, a[n-1]] Rotate once The result is an array [a[n-1], a[0], a[1], a[2], …, a[n-2]] .

Example 1：

 Input ：numbers = [3,4,5,1,2]
 Output ：1

Example 2：

 Input ：numbers = [2,2,2,0,1]
 Output ：0

Two 、 Problem solving

Two points search

This question has duplicate numbers , There are three situations
The median == Right value ：right -= 1;
The median < Right value ： right = mid;
The median > Right value ：left = mid + 1;

class Solution {
    
    public int minArray(int[] numbers) {
    
        // This question contains repeated numbers , So there are three cases 
        int left = 0,right = numbers.length - 1;
        while(left < right){
    
            int mid = left+(right - left) / 2;
            if(numbers[mid] < numbers[right]){
    
                right = mid;
            }else if(numbers[mid] > numbers[right]){
    
                left = mid + 1;
            }else{
    
                right -= 1;
            }
        }
        return numbers[left];
    }
}

Time complexity ：O(log(n);

Spatial complexity ：O(1).