153. Find-Minimum-in-Rotated-Sorted-Array

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output:
 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output:
 0

Method One

我们相当于一次检查 pivot - 1, pivot , pivot + 1 三个点。 由于我们的模板，不可能让 pivot 处于 最后的位置，所以 pivot + 1 不能够超出范围。 而 pivot - 1

class Solution {
  public int findMin(int[] nums) {
    if (nums.length == 1) {
      return nums[0];
    } // 这个是为 mid + 1 排雷，如果有两个元素， mid + 1 就不会超出范围。

    int left = 0, right = nums.length - 1;

    if (nums[right] > nums[0]) {
      return nums[0];
    } // 这个是防止本身就有序的，为后面 mid - 1 排雷。


    while (left <= right) {
      int mid = left + (right - left) / 2;

      if (nums[mid] > nums[mid + 1]) {
        return nums[mid + 1];
      }

      if (nums[mid - 1] > nums[mid]) {
        return nums[mid];
      }

      // if the mid elements value is greater than the 0th element this means
      // the least value is still somewhere to the right as we are still dealing with elements
      // greater than nums[0]
      if (nums[mid] > nums[0]) {
        left = mid + 1;
      } else {
        // if nums[0] is greater than the mid value then this means the smallest value is somewhere to
        // the left
        right = mid - 1;
      }
    }
    return 10000;

}
}

class Solution {
    public int findMin(int[] nums) {
        if(nums.length == 1) return nums[0];
        int left = 0;
        int right = nums.length - 1;
        
        if(nums[left] < nums[right]) return nums[left];
        
        while( left <= right ) {
            int pivot = left + ( right - left ) / 2;
            
            if( nums[pivot] > nums[pivot + 1]) {
                return nums[pivot + 1];
            }
            if( nums[pivot] < nums[pivot - 1]) {
                return nums[pivot];
            }
            
            if( nums[left] < nums[pivot] ) {
                left = pivot + 1;
            }
            
            if( nums[right] > nums[pivot]) {
                right = pivot;
            }
        }
        
        return 10000;
    }
}
​

2022 思考的答案

class Solution {
    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while(lo <= hi){
            int mid = (lo + hi) >>> 1;
            boolean wantTrue = nums[mid] >= nums[0];
            if(wantTrue){
                lo = mid + 1;
            }else{
                hi = mid - 1;
            }
        }
        return lo == nums.length ? nums[0] : nums[lo];
    }
}