题解 | 旋转数组的最小数字

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int minNumberInRotateArray (int[] nums) {
        // write code here
        if(nums.length==0) return 0;
        int l=0;
        int r=nums.length-1;
        while(l<r){
            int m=l+(r-1)/2
            if(nums[m]>nums[r]){
                l=m+1;// 中点在大值部分，最小值在右侧
            }
            else if(nums[m]<nums[r]){
                r=m; //中点在小值部分，最小值在左侧或者就是中点
            }
            else{
                r--; // 相等时，无法判断，保守缩小范围
            }
        }
        return nums[l];
    }
}

这里只解释为什么选择右端点作为比较值。

1 2 3 4 5 如果选择左端点作为比较值，mid=3，target=1,答案在mid的左边

3 4 5 1 2 mid=5 ，target=3，答案却在mid的右边。这样会导致无法通过中点值来判断最小值的位置。而选择右端点作为比较值，右端点始终是靠近最小值的。