Suppose the array sorted in ascending order is rotated at some previously unknown point. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Please find the smallest element.

You can assume that there are no duplicate elements in the array.

Example 1:

Input:3.4.5.1.2] output:1
Copy the code

Example 2:

Input:4.5.6.7.0.1.2] output:0
Copy the code

So we’re going to find the smallest value in an ascending sort array after rotation, which is essentially the smallest value in the array. Therefore, the key is to find the mutation point nums[I] > NUMs [I + 1.

One method is to iterate through the rotated array, find the mutation point index by comparing nums[I] with NUMs [I + 1], and return the element at index.

class Solution {
    public int findMin(int[] nums) {
        if(nums == null) {return 0;
        }

        int index = 0;
        for(int i = 0; i < nums.length - 1; i++){
            if(nums[i] > nums[i + 1]){
                index = i + 1;
                break; }}returnnums[index]; }}Copy the code

We can also use double Pointers, with left and right pointing to both ends of the array:

  • ifnums[left] < nums[right]If this is true from the beginning, then the array is in strict ascending order and returns directlynums[left]
  • Otherwise, keep movingrightUntil thenums[left] < nums[right], thennums[right + 1]It’s the smallest element
class Solution {
    public int findMin(int[] nums) {
        if(nums == null) {return 0;
        }

        int left = 0;
        int right = nums.length - 1;
        if(nums[left] <= nums[right]){
            return nums[left];
        }

        while(left <= right){
            if(nums[left] > nums[right]){
                right--;
            }else{
                return nums[right + 1]; }}return 0;
    }   
Copy the code

We can also use binary lookup, which is similar in idea to the double pointer above, with middle denoting the midpoint of the array:

  • ifnums[middle] > nums[0],nums[left:middle]Is in strict ascending order, should be fromnums[middle + 1, right]Continue to look for
  • Otherwise, continue inrightLeft innums[left:right]To look for
  • In the end,nums[left]That’s the smallest value in the array
class Solution {
    public int findMin(int[] nums) {
        if(nums == null) {return 0;
        }

        int left = 0;
        int right = nums.length - 1;
        if(nums[left] < nums[right]){
            return nums[left];
        }
            
        while(left < right){
            int middle = left + (right - left) / 2;
            if(nums[middle] < nums[0]){
                right--;
            }else{
                left = middle + 1; }}returnnums[left]; }}Copy the code