剑指 Offer 11. && LeetCode 154. 旋转数组的最小数字-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指 Offer 11. && LeetCode 154. 旋转数组的最小数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考资料：LeetCode 官方解答

剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

示例 1：

输入：numbers = [3,4,5,1,2]
输出：1
示例 2：

输入：numbers = [2,2,2,0,1]
输出：0

===================================
思路：
注意到旋转后的数组最小值与最右端的值之间特征
在最小值右边的值都小于等于最右端的值；
在最小值左边的值都大于等于最右端的值。
用二分法，
如果中间值小于右端值，说明中间值落在了最小值右边（或重合），即最小值在左边的一半数组中（或重合）；
如果中间值大于右端值，说明中间值落在了最小值左边, 即最小值在右边的一半数组中；
如果中间值等于右端值，此时最小值可能落在左半数组（ 2 2 1 2 2 2 2），也有可能落在右半数组（ 2 2 2 2 1 2 2 ）/ / 描黑的数表示中间值;
考虑到while(l<r), m=(r+l)/2, m不可能等于r, 所以在“ 中间值等于右端值”的情况下，我们可以令r=r-1, 表示删掉一个重复数，重新开始二分查找。
直到l==r,区间收缩到一个点上，那个点就是答案。文章来源地址https://www.toymoban.com/news/detail-488267.html

class Solution {
    public int minArray(int[] nums) {
        int l=0;
        int r = nums.length-1;
        int m = 0;
        
        while(l<r){
            m = (l+r)>>1;
            if(nums[m]<nums[r]){ // rihgt order                
                r=m;
            }else if(nums[m]>nums[r]){// // left order
                l=m+1;
                
            }else{
                r=r-1;
            }
        }
        return nums[r]; // or nums[l]
    }
}