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 sample1: Input: [3.4.5.1.2] output:1The sample2: Input: [2.2.2.0.1] output:0
Copy the code

Method one:

Analysis: Sort the array first, then fetch the first element

Array.sort()

Sort array elements

The profile

array.sort()

array.sort(orderfunc)

parameter

Orderfunc: An optional function to specify how to sort

The return value

A reference to the array. Note that we are sorting in the original array, not creating a new array

describe

The sort () method sorts the array elements in the original array without creating a new array. If you call sort () without arguments, the elements in the array are sorted alphabetically (or, more precisely, in character encoding order). To do this, you first convert the element to a string, if necessary, for comparison

If you want to sort in any other order, you must provide a comparison function that compares two values and returns a number indicating the relative order of the two values. The comparison function takes two arguments, a and b, and returns the following values

  • A value less than 0. In this case, it means that a is less than B by sorting criteria and that a should precede B in the sorted array
  • 0. In this case, a and B are equal
  • A value greater than 0. In this case, a is greater than B.

Note: undefined elements are always arranged at the end of the array. This is true even if a custom comparison function is provided, because the Underpay values will not be passed on to the provided OrderFunc.

The sample

The following code shows how to write a comparison function to sort a value numerically rather than alphabetically:

// Sort function for numeric sort
function numberorder(a,b){ return a-b}
a=new Array(33.4.222.1111);
a.sort();// Alphabetical order: 1111, 2222, 33, 4
a.sort(numberorder);// numeric sort: 4,33,222,1111
Copy the code

code

/ * * *@param {number[]} numbers
 * @return {number}* /
var minArray = function(numbers) {
    return numbers.sort(function(a,b){
        return a-b
    })[0]};Copy the code

Method 2:

Analysis: Use dichotomy to traverse a set of numbers

Ideas:

  1. Take an arrayleftwithrightThe midpoint betweenmid.leftIs zero,rightIs the array length -1,midTake down the whole
  2. letnumbers[mid]withnumbers[right]Why can’t we make it herenumbers[mid]withnumbers[left]Compare? The reason is simple, for example: give two rotated arrays,1,1,0,1 [1].,0,2,2,2 [2], for both arrays, the minimum value of the first array0Located in themidwithrightIs the minimum value of the second array0Located in theleftwithmidFrom these two arrays alone, it is not very good to see which range the minimum value is in, so select letnumbers[mid]withnumbers[left]The comparison)
  3. If numbers[mid]>numbers[right], the minimum value is in arraymidandrightThe interval between, let’sleft=mid+1

4. If numbers[mid]<numbers[right], the minimum value is in arrayleftandmidThe interval between, let’sright=mid If numbers[mid]==numbers[right]; if numbers[mid]==numbers[right This is the time to letRight from the reduction, that is, to reduce the range of the array, improve the accuracy (why notLeft the increase?If you increment left, you get an array like [1,0,1,1,1].If you want left to increment, you’re going to miss the answer, so you have to subtract right

code

/ * * *@param {number[]} numbers
 * @return {number}* /
var minArray = function(numbers) {
    let left=0;
    let right=numbers.length-1;
    
    while(left<right){
        // round down
        let mid=Math.floor((left+right)/2);
        if(numbers[mid]<numbers[right]){
            right=mid;
        }else if(numbers[mid]==numbers[right]){
            right--
        }else{
            left=mid+1}}return numbers[left]
}
Copy the code