LeetCode hot100-67-N

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

153. 寻找旋转排序数组中的最小值
已解答
中等
相关标签
相关企业
提示
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

class Solution {
    public int findMin(int[] nums) {
        int l=0,r=nums.length-1;
        //int min = nums[0];
        while(l<r){
            int mid=(l+r)/2;
            // 在左边
            if(nums[mid]<nums[r]){
                r=mid;
            // 在右边
            } else{
                l=mid+1;
            }

        }
        return nums[l];
        
    }
}

为什么不能更新high = mid - 1？

想象一种情况，【4, 5, 6, 0, 1, 2, 3】这个数组右半段为0, 1, 2, 3，左半段为4,5,6, 第一次判断中点mid将落在0的位置，此时若：

令high = mid -1。你会发现出了问题，因为此时的high变成了0元素的前一位：元素6的位置！而low位置没动，新的数组变成了【4, 5, 6】，这样我们就把最小值0漏掉了。

为什么中间元素与右边元素比较，而不是与左边元素比较。解释如下

原文地址：https://blog.csdn.net/alike_meng/article/details/144430329

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！