The title

Moving the beginning elements of an array to the end of the array is called array rotation. Take a rotation of an incrementally sorted array and print the smallest element of the rotation array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], whose minimum value is 1.

Example 1:

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

Example 2:

Input: [2,2,2,0,1] output: 0

Train of thought

I had an idea at the beginning, because this is a rotated ordered array, the minimum value must be less than the number in front of it, so we just need to find the first number that doesn’t obey the ascending order, and if we don’t find it, we return the first number in the array.

class Solution {
public :
int minArray(vector<int>& numbers) {
        for (int i = 0; i < numbers.size() - 1; i++) {
            if (numbers[i] > numbers[i + 1]) return numbers[i + 1];
        }
        return numbers[0];// return the first sequence}};Copy the code

Of course you can be lazy, sort it and just return the first number (you can write it yourself, merge it)

class Solution {
public:
    int minArray(vector<int>& numbers) {
        sort(numbers.begin(),numbers.end());
        return numbers[0]; }};Copy the code

But actually, if you have an ordered or semi-ordered sequence, you should think about binary search. The last element of the rotated array has the property that the number to the left of the minimum must be greater than it, and the number to the right of the minimum must be less than it, and we can divide by that

  • whennumbers[r] > numbers[mid], the minimum value must be to the left of the midpoint or the midpoint, so the range to the right of the midpoint can be discarded
  • whennumbers[r] < numbers[mid], the minimum value must be to the right of the midpoint, so the range to the right and left of the midpoint can be discarded
  • whennumbers[r] == numbers[mid], can not determine the specific range of the minimum value, reduce the boundary, and then dichotomy
class Solution {
public:
    int minArray(vector<int>& numbers) {
        / / binary
        int l = 0, r = numbers.size() - 1;
        while(l < r){
            int mid = (l + r) >> 1;
            // The number to the left of the minimum must be greater than it, and the number to the right of the minimum must be less than it
            if(numbers[r] > numbers[mid]) r = mid;//
            else if(numbers[r] == numbers[mid]) r--;//
            else l = mid + 1;//
        }
        returnnumbers[l]; }};Copy the code