【二分查找专题】剑指 Offer 11. 旋转数组的最小数字-跟着帅地玩副业，开拓第二曲线PlayOffer

小肸永久会员 2023年9月6日上午9:48

class Solution {
    public int minArray(int[] numbers) {
        //首先，数组是递增，所以最小值x是数组的第一个元素
        //不过数组旋转了一次，所以x的下标可能在数组中的任意位置
        //所以对于[l, r]这个范围内，以右边界也就是数组最后一个元素nums[r]为比较值，来二分
        //理论上在最小值右侧的元素都是大于等于nums[r]，在最小值左侧的元素都是小于等于nums[r],所以
        //1.nums[mid] > nums[r]：最小值在右部分（因为nums[mid]位于最小值的左侧）
        //2.nums[mid] < nums[r]：最小值在左部分（并且最小值可能是nums[mid]）（因为nums[mid]位于最小值的右侧）
        //3.因为包含重复元素，所以nums[mid]可能等于nums[r]，比如是【2，2，2，1，1，2，2，2，2】这样的序列，
        //但无法确定nums[mid]是在最小值的右侧还是左侧，但nums[mid]==nums[r]，所以nums[r]有一个替代品就是nums[mid]，
        //所以可以忽略nums[r]这一个元素，所以这个算法的最坏时间复杂度是O(N)，【1，1，1，1，1，1，1】这样的序列。
        int l = 0, r = numbers.length - 1;
        while (l <= r) {
            int mid = (l + (r - l) / 2);
            if (numbers[mid] < numbers[r]) {
                //左半部分找
                r = mid;
            } else if (numbers[mid] > numbers[r]) {
                //右半部分找
                l = mid + 1;
            } else {
                //无法确定在左边还是右边，所以缩小右边界
                r --;
            }
        }
        return numbers[l];
    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年9月4日上午8:42

//1.暴力遍历法，找到第一次出现后面大于前面的位置进行返回
//2.二分查找

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size()-1;
        while(low<high){
            int mid = low + (high-low)/2;
            if(numbers[mid]<numbers[high]){ // 中间值小于右边，代表右侧是有序的，故中断点应在左边
                high = mid; // 此处无法判断mid所指元素是否为最小值，故第二轮mid所指的值仍要加进考虑
            }
            else if(numbers[mid]>numbers[high]){ // 中间值大于右边，代表右侧是无序的，中断点在右侧
                low = mid+1; // 此处可以判断mid所指值必然不是最小值，故第二轮mid所指的值无需加入考虑
            }
            else{ // 此处代表当选取的中间点等于右边的点时
                high -= 1; // 此时无法判断所求值是在左边还是在右边，于是将高位指针移一位进行遍历
            }
        }
        return numbers[low];
    }
};

0 赞同 0 条回复

Sheng 永久会员 2023年9月2日下午8:03

相等的时候一直不知道怎么处理，看的答案

“`java//寻找旋转数组的最小值
class Solution {
public int minArray(int[] numbers) {

    int l = 0;
    int r = numbers.length - 1;
    int end = numbers[r];
    int mid = -1;
    while (l < r) {
        if(numbers[l] < numbers[r]) 
            return numbers[l];//可能在剪除过程中出现排序数组

        mid = (l + r) / 2;
        if(numbers[mid] > numbers[r]) {
            l = mid + 1;
        }
        else if(numbers[mid] < numbers[r]) {
            r = mid;//不能减一
        }
        else {//numbers[mid] == numbers[r]
            l++;//相等的时候，往右走一个点

        }
    }
    return numbers[l];
}

}

“`

0 赞同 0 条回复

sincere 普通 2023年8月31日下午11:05

思路：假设分为左右序列，分别递增，则右序列的最大值即nums[length-1]小于等于右序列任意值，转折点就是最小值，二分查找时如果nums[mid]>nums[right]说明在mid左序列，需要左区间逼近，nums[mid]<nums[right]说明在右序列，需要右区间逼近，如果等于可能就是right也可能在左边，可以将right缩小一位范围
复杂度：时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public int minArray(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while ( left < right) {
            int mid = left + ( right - left) / 2;
            if ( nums[mid] > nums[right] ){// mid在左序列 偏小
                left = mid+1;
            }else if(nums[mid]<nums[right]){//mid在右序列 偏大
                right = mid;
            }else{// 缩小right范围
                right--;
            }
        }
        return nums[left];
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年8月28日下午11:49

当mid等于right时，无法判断mid是在左排序数组中还是在右排序数组中，因此，右指针往左移一位，缩小范围。
例：[4,5,3,3,3]，[3,3,1,3]

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length-1;
        while(left < right){
            int mid = (left + right)/2;
            if(numbers[mid] > numbers[right]){
                left = mid+1;
            }else if(numbers[mid] < numbers[right]){
                right = mid;
            }else{
                right--;
            }
        }
        return numbers[right];
    }
}

0 赞同 0 条回复

JustRtn 普通 2023年8月28日下午8:15

使用二分思想
注意：
循环结束条件：low < high
numbers[mid] < numbers[high]情况下不能排除mid本身
相等情况下仅缩小比较点本身（这里是high)
时间复杂度：最坏O(n)，平均O(log (n));

class Solution {
public:
    int minArray(vector& numbers) {
        int low = 0;
        int high = numbers.size() - 1;

        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (numbers[mid] < numbers[high]) {
                high = mid;
            } else if (numbers[mid] > numbers[high]) {
                low = mid + 1;
            } else {
                high--;
            }
        }
        return numbers[low];
    }
};

0 赞同 0 条回复

c 普通 2023年8月28日下午8:11

二分

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

0 赞同 0 条回复

行动派小彩笔普通 2023年8月28日下午3:18

//二分思想，时间复杂度O(logn)
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size()-1;
        while(left<right)
        {
            int mid=(left+right)/2;
            if(numbers[mid]>numbers[right]) left=mid+1;
            else if(numbers[mid]==numbers[right]) right--;
            else right=mid;
        }
        return numbers[right];
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年8月28日下午2:52

看完讲解才知道重复怎么处理

class Solution {
    public int minArray(int[] numbers) {
        int l = 0;
        int r = numbers.length - 1;
        //二分查找核心是范围缩小，而不是每次都减一半
        while (l < r) {
            if(numbers[l] < numbers[r]){
                return numbers[l];
            }
            int mid = (r - l) / 2 + l;
            if (numbers[mid] > numbers[l]) {
                l = mid + 1;
            } else if (numbers[mid] < numbers[l]) {
                r = mid;
            } else {
                //说明存在重复元素了，至少可以往左砍一刀
                l++;
            }
        }
        return numbers[l];

    }
}

0 赞同 0 条回复

【二分查找专题】剑指 Offer 11. 旋转数组的最小数字

共以下 9 个回答

# 回答此问题取消回复

【二分查找专题】剑指 Offer 11. 旋转数组的最小数字

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复