“This is my 32nd day of participating in the First Challenge 2022. For details: First Challenge 2022”

11. Rotate the smallest number in the array

The title

Moving the beginning elements of an array to the end of the array is called array rotation.

You are given an array of numbers that may have duplicate elements. It was originally an array in ascending order, rotated once as described above. Return the smallest element of the rotated 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: 1Copy the code

Example 2

Input: [2,2,2,0,1] output: 0Copy the code

Answer key

At first glance, the problem looks simple, one line of code

var minArray = function(numbers) { return Math.min(... numbers) };Copy the code

And if you look at it, it turns out it’s a dichotomy. One line of code is simple, but time is O(N); And now they tell us that the array is sorted but it’s been reversed. Take advantage of the fact that arrays are ordered in a certain range.

Words dichotomy is really want to think more understanding ah, this topic play dichotomy flower came.

dichotomy

An array is an inverted array; What are the conditions for splitting an array?

Suppose the left pointer is leftleftLeft and the right pointer is rightrightright. And the minimum value is in [left,right][left,right][left,right] interval

Numbers [right]numbers[right]numbers[right] numbers[right]

  • Numbers [right]numbers[right]numbers[right] numbers[right]numbers[right]
  • Numbers [right]numbers[right]numbers[right] numbers[right]numbers[right]

[left,right][left,right][left,right] midmidmid

  • If numbers[mid]>numbers[right] numbers[mid]>numbers[right] numbers[mid]>numbers[right] Midmidmid falls to the left of the minimum; The minimum value is between mid+1,right [mid+1,right][mid+1,right]
  • Numbers [mid]==numbers[right]numbers[mid] ==numbers[right]numbers[mid] ==numbers[right]numbers[mid] ==numbers[right] The minimum value is in the range [left,right−1] [left,right-1][left,right−1]
  • Neither of the above may be the smallest element except in [left,mid][left,mid][left,mid]
var minArray = function (numbers) {
  let len = numbers.length
  let left = 0
  let right = len - 1
  while (left < right) {
    let mid = Math.floor(left + (right - left) / 2)
    if (numbers[mid] > numbers[right]) {
      left = mid + 1
    } else if (numbers[mid] == numbers[right]) {
      right = right - 1
    } else {
      right = mid
    }
  }
  return numbers[left]
}
Copy the code

conclusion

The author’s level is limited, if you have any opinions and suggestions, please leave a comment in the comment section