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.

The subject sample

Example 1:

Input: [3,4,5, 2] Output: 1Copy the code

Example 2:

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

Subject analysis

Because the given array is incrementally sorted, it doesn’t make any sense to take the smallest value in the array. Rotating arrays can reduce time complexity based on the given condition -> increasing sort. We can do this with dichotomy, but the point is to find the boundary conditions.

  • So let’s find mid
  • And then compare it to the rightmost value

Code implementation

/ * * *@param {number[]} numbers
 * @return {number}* /
var minArray = function(numbers) {
    let left = 0;
    let right = numbers.length -1
    while(left <= right) {
        let mid = left + right >>> 1
        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

Title source

11. Rotate the smallest number in the array