Leetcode -- minimum number of rotation array

subject ：

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.

Example 1：

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

Example 2：

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

Ideas ：

How do you look at this question , Is to find the minimum value in the array , There are many solutions for finding the minimum , The simplest is to use a min Function done , But you can't do that in an interview , This question has a better idea , Binary search .

Why is binary search ？

Array in question , The first is the rotation of the ordered array , There is a certain degree of order , There is another key feature , The first element will be greater than or equal to the last element , Take this condition as the entry of the loop , Conditions for exiting the loop , When the high and low pointers meet , I found the smallest one .

Of course, there are several special cases ,

1. An ascending array that has not been rotated , At this time, the smallest is the first element ;eg1.[1,3,5]

2.   The boundary condition when there is only one element ;eg2.[1]

3.  When there are many repetitions , You have to return to the original order to find .eg3.[3,1,3,3,3]

The code is as follows ,

int minArray(vector<int>& numbers) {
        int start = 0, end = numbers.size() - 1;
        int mid = start;        //  For the case of ascending order without rotation , Directly return the initial value , That's the minimum 

        while (numbers[start] >= numbers[end]) {
            if  (end-start == 0){    //  The boundary condition when there is only one element 
                mid = end;
                break;
            }
            if (end - start == 1) {    //  Conditions for exiting the loop , When the high and low pointers meet , I found the smallest one 
                mid = end;
                break;
            }
            mid = (start + end) / 2;

            if (numbers[start] == numbers[end] && numbers[mid] == numbers[end]) {
                return order(numbers, start, end);    //  When there are many repetitions , You have to return to the original order to find 
            }
            if (numbers[mid] > numbers[end])
                start = mid;
            else if (numbers[mid] <= numbers[end])
                end = mid;
        }

        return numbers[mid];
}

int order(vector<int>& numbers, int start, int end) {
        int result = numbers[start];
        for (int i = start + 1; i <= end; i++) {
            if (numbers[i] < result) {
                result = numbers[i];
            }
        }
        return result;
}