Topic:Rotate the smallest number in the array

Description: To move the beginning elements of an array to the end of the array, we call rotation of the array. 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: 0Copy the code

Solution: dichotomy

Source: Krahets

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        returnnumbers[i]; }}Copy the code

Complexity analysis:

  • Time complexity: In special cases (e.g. [1,1,1,1] [1,1,1]), will degenerate to.
  • Spatial complexity ： Pointers use extra space of constant size.

Numbers [m] == numbers[j]