Topic describes

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

1. Violent search

Because it is to rotate the ordered array and loop the array, the normal increasing sequence arr[I] must be less than arr[I +1]. When ARr [I] > arr[I +1], it indicates that this position is the starting point of rotation, which is also the minimum value of the array time complexity: O(n)

Example code 1:

def minArray1(numbers: [int]) - >int:
    for i in range(len(numbers) - 1) :if numbers[i] > numbers[i + 1] :return numbers[i + 1]
    return numbers[0]
Copy the code

2. Dichotomy

Or according to the characteristics of the rotation point, we can use dichotomy to determine.

  1. If arr[m] < arr[r], it indicates that the data of m-r is ordered, then the rotation point is between L-M, and r is assigned to M
  2. If arr[m] > arr[r], it indicates that the data segment of m-r is disordered, then the rotation point is between r-m, and l is assigned to m+1
  3. Finally, if l <= r, the binary traversal is complete, and arr[l] is the rotation point

Time complexity: O(log2N)

Example Code 2

def minArray(numbers: [int]) - >int:
    l, r = 0.len(numbers) - 1
    while l < r:
        m = l + (r - l) // 2
        print("idx", l, r, m)
        if numbers[m] < numbers[r]:
            r = m
        elif numbers[m] > numbers[r]:
            l = m + 1
        else:
            r -= 1
    return numbers[l]
Copy the code

Example Illustration 2

Initial position, L, M, R

  1. 6 > 3 means the rotation point is on the right, L= M+1
  2. 5 < 6, that means the rotation point is on the left, R = M
  3. 4 < 5, that means the rotation point is on the left, R = M
  4. At the end of traversal, arr[L] is found to be the rotation point