Sword finger offer 11. rotate the minimum number of the array

https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

Solution 1 ：
Violence law , Go through the array directly , Find the maximum value

class Solution {
    
    public int minArray(int[] numbers) {
    
        int min=Integer.MAX_VALUE;
        for(int number:numbers){
    
            if(number<min){
    
                min=number;
            }
        }
        return min;
    }
}
//O(n)
//O(1)

class Solution {
    
public:
    int minArray(vector<int>& numbers) {
    
        int min=INT_MAX;
        for(int num:numbers){
    
            if(num<min){
    
                min=num;
            }
        }
        return min;
    }
};
//O(n)
//O(1)

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        min=10000
        for num in numbers:
            if num<min:
                min=num
        return min

Solution 2 ： Two points search

For the number after rotation , Although the array as a whole is not ordered , But the array is divided into two parts , These two parts must be in order , With numbers = [3,4,5,1,2] For example ,3 4 5 It's in ascending order ,1 2 It's in ascending order , That is, the array is divided into two parts in order , They are respectively called left half order and right part order , The smallest number is the first number in the right half

The rightmost number must belong to the right half of the order , Put the rightmost element nums[r] And intermediate elements num[mid] Compare , Divided into the following 3 In this case ：

1. nums[r]<nums[mid]: mid It belongs to the left half of the order , The minimum number belongs to the interval [mid+1,r] mid It can't be the smallest number , Therefore, the interval does not contain mid
2. nums[r]>nums[mid]: mid It belongs to the right half of the order , The minimum number belongs to the interval [left,mid] mid May be the smallest number , Therefore, the interval contains mid
3. nums[r]==nums[mid]: Because there are duplicate elements in the array , Do not return directly at this time , Instead, narrow the right boundary

There is no peace here nums[i] The reason for the comparison is because the leftmost element at the beginning nums[i] It is not certain whether it belongs to the left half of the ordered array or the right half of the ordered array

class Solution {
    
    public int minArray(int[] numbers) {
    
        int left=0,right=numbers.length-1;
        while(left<right){
    
            int mid=left+(right-left)/2;
            if(numbers[mid]>numbers[right]){
    
                left=mid+1;
            }else if(numbers[mid]<numbers[right]){
    
                right=mid;
            }else if(numbers[mid]==numbers[right]){
    
                right--;
            }
        }
        return numbers[left];
    }
}
//O(logn)
//O(1)

class Solution {
    
public:
    int minArray(vector<int>& numbers) {
    
        int l=0,r=numbers.size()-1;
        while(l<r){
    
            int m=l+(r-l)/2;
            if(numbers[m]>numbers[r]){
    
                l=m+1;
            }else if(numbers[m]<numbers[r]){
    
                r=m;
            }else if(numbers[m]==numbers[r]){
    
                r--;
            }
        }
        return numbers[l];
    }
};

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left=0
        right=len(numbers)-1
        while left<right:
            mid=left+(right-left)//2
            if numbers[mid]>numbers[right]:
                left=mid+1
            elif numbers[mid]<numbers[right]:
                right=mid
            elif numbers[mid]==numbers[right]:
                right-=1
        return numbers[left]