The topic of dry

Given an array of length N, sorted in ascending order, rotated 1 to n times, the input array is obtained. For example, the original array nums = [0,1,2,4,5,6,7] might be changed to: If you rotate it four times, you get [4,5,6,7,0,1,2] and if you rotate it seven times, you get [0,1,2,4,5,6,7] Array [a [0], a [1], a [2],… and a [n – 1]] array to the result of the rotation a [a] [n – 1, a [0], a [1], a [2],… and a [n – 2]].

You are given an array nums with different element values. It was originally an array sorted in ascending order and rotated several times as described above. Find and return the smallest element in the array.

Example 1:

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

Solution 1: One cycle

I’m just going to iterate, the next value is less than our current value and the next value is what we’re going to find

Execution time: 88 ms, beating 48.68% of all JavaScript commits

Memory consumption: 37.7 MB, beating 93.38% of all JavaScript commits

Code implementation:

  var findMin = function (nums) {
    let length = nums.length
    for (let i = 0; i < length; i++) {
      if (nums[i] > nums[i + 1]) {
        return nums[i + 1]}}return nums[0]};Copy the code

Solution 2: dichotomy

Just recognize that the right-most number is always smaller than the left-most number, and the left-most number is always larger than the right number

So when we binary search, if the current mid value is greater than the Max value, it indicates that the current mid is in the left range, then min=mid+1; On the other hand, if our mid is less than our Max, that means we’re in the right interval, so we want Max =mid, because we’re looking for the beginning of the right interval, and so on. Eventually our min will end up at the minimum.

Code implementation:

Execution time: 80 ms, beating 83.82% of users in all JavaScript commits

Memory consumption: 38.6 MB, beating 23.98% of all JavaScript commits

 var findMin = function (nums) {
    let low = 0;
    let max = nums.length - 1;
    while (low < max) {
      let  mid = Math.floor((max + low) / 2)
        if (nums[mid] > nums[max]) {
            low = mid + 1
        } else {
            max = mid
        }
    }
    return nums[low]
};
Copy the code