LeetCode 153. 寻找旋转排序数组中的最小值

题目链接：

力扣https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

【分析】最小值就是产生断点的位置，这个点的特征就是nums[mid - 1]>nums[mid]

class Solution {

    int[] nums;
    int n;
    int ans = 0;

    public void binarySearch(int left, int right){
        if(left > right) return;
        int mid = (left + right) >>> 1;
        if(mid == 0) {
            if(nums[mid] > nums[mid + 1]) {
                ans = mid + 1; return;
            }
        }
        else if(mid == n) {
            if(nums[mid] < nums[mid - 1]){
                ans = mid; return;
            }
        }
        else{
            if(nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1]){
                ans = mid; return;
            }else{
                binarySearch(left, mid - 1);
                binarySearch(mid + 1, right);
            }
        }
    }
    
    public int findMin(int[] nums) {
        this.n = nums.length - 1;
        if(n == 0) return nums[0];
        this.nums = nums;
        binarySearch(0, n);
        return nums[ans];
    }
}

【改进】上面的判断过于复杂了，其实可以直接通过判断mid和right的大小来缩短区间。

     *
  *
*
              *
           *
        *

旋转后的数组大小大概这样，如果mid为前半部分，那么他肯定>right，去[mid+1, right]部分找即可；如果mid在右半部分，那么他一定

class Solution {

    public int[] nums;

    public int binarySearch(){
        int n = nums.length;
        int left = 0, right = n - 1, mid = 0;
        while(left < right){
            mid = (left + right) >>> 1;
            if(nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }

    public int findMin(int[] nums) {
        this.nums = nums;
        return binarySearch();
    }
}

注意：这里最重要的是二分查找的边界和细节，

     #
  *
*
              *
           *
        *

我们可以发现，当mid>right的时候，可以直接去left = mid + 1部分找，但是当mid