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

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路
2、给出时间和额外空间复杂度

shuaidi

更新于 4 年前 181 33

共以下 33 个回答

cute. 普通 2023年4月3日下午4:51

var minArray = function(numbers) {
    let left =0,
    right = numbers.length-1;
    while(left<right) {
        let middle = Math.floor((right+left)/2)
        if( numbers[middle] < numbers[right]) {
            // 说明最小数在左边
            right = middle
        } else  if(numbers[middle] > numbers[right]) {
            left = middle+1
        } else {
            right--
        }
    }
    return numbers[left]
};

0 赞同 0 条回复

宁永久会员 2023年1月14日下午1:36

class Solution {
    public int minArray(int[] numbers) {
        int l = 0;
        int r = numbers.length - 1;

        while(l < r){
            if(numbers[l] < numbers[r])//处理过程中的极端情况0 1 2所以得放到循环里面
                return numbers[l];
            int mid = (r - l) / 2 + l;
            if(numbers[mid] < numbers[l]){//比较中间值和左指针的大小
                r = mid;
            } else if(numbers[mid] > numbers[l]){
                l = mid + 1;
            } else{
                l = l + 1;
            }
        }
        return numbers[l];
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月9日下午2:03

def minArray(numbers):
    l = 0
    r = len(numbers) - 1


    while l < r:
        # 极端情况下旋转后或者经过砍后变成了原数组（递增的）
        if numbers[l] < numbers[r]:
            return numbers[l]
        # 防止使用（r+l）// 2 溢出,不过这道题的条件不会溢出
        mid = l + (r - l) // 2
        # 旋转后数组的第一个元素一定比最小数字后的数大（因为最小值左边的数一定比右边的数大）这里如果mid值大于第一个元素，说明mid在最小值左边，砍掉mid前所有的数，就算mid正好是最小值的前一个，砍完后就是递增数组
        if numbers[mid] > numbers[l]:
            l = mid + 1

        elif numbers[mid] < numbers[l]:
            r = mid
        else:
            # numbers[mid] = numbers[l] 这种情况说明数组中存在重复的数字，但由于mid是向下取整的，所以得到的mid不可能等于r，但有可能等于l，所以mid是在[l，r-1]间的，同时mid又与数组的
            #第一个元素相等，为了保证不会砍掉最小值，只将左边界右移一个位置
            l = l + 1

    return numbers[l]

0 赞同 0 条回复

lucca 普通 2023年1月7日下午4:31

class Solution {
    public int minArray(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[r]) l = mid + 1;
            else if (nums[mid] < nums[r]) r = mid;
            else r--; 
        }
        return nums[l];
    }
}

时间复杂度：O(N)
空间复杂度：O(1)

0 赞同 0 条回复

Gg 普通 2022年12月31日下午9:58

class Solution {
    public int minArray(int[] numbers) {
        // 有数组的顺序规律，得出可用二分查找
        int i = 0;
        int j = numbers.length - 1;
        while(i < j){
            int m = i + (j-i) / 2;
            if(numbers[m] >= numbers[j]){
                // 中间值大于最后一个，说明最小值在右边
                i = m + 1;
            }else if(numbers[m] < numbers[j]){
                // 中间值小于最后一个，说明最小值在左边
                j = m;
            }else{
                // 中间值等于最后一个，可能本身就是最小值,j-1进行范围缩小
                j = j-1;
            }
        }
        return numbers[i];
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:25

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int i = 0;
        int j = numbers.size()-1;
        while(i<j){
            int m = i + (j-i)/2;
            if(numbers[m] < numbers[j]){
                //说明旋转点在m的左边
                j = m;
            }else if(numbers[m] > numbers[j]) i = m+1;//说明旋转点在m右边
            else j--;
        }
        return numbers[i];
    }
};

0 赞同 0 条回复

xye 普通 2022年11月23日下午4:16

func minArray(numbers []int) int {
    l := 0
    r := len(numbers) - 1
    var m int
    for l < r {
        m = l + (r - l) / 2
        //判断在左序列还是右序列
        if numbers[m] > numbers[r] {
            l = m + 1
        }else if numbers[m] < numbers[r] {
            r = m
        }else{
            r = r - 1
        }
    }
    return numbers[l]
}

时间O(log2N) 空间O(1)

0 赞同 0 条回复

刺猬普通 2022年11月22日下午12:55

class Solution {
public:
    int minArray(vector<int>& numbers) {
        if(numbers.front() < numbers.back())
            return numbers.front();
        int l = 0;
        int r = numbers.size() - 1;
        int mid;
        while(l < r) {
            mid = (l + r) / 2;
            if(numbers.at(mid) > numbers.at(r))
                l = mid + 1;
            else { 
                if(numbers.at(mid) < numbers.at(r))
                    r = mid;
                else
                    r = r - 1;
            } 
        }
        return numbers.at(l);
    }
};

时间复杂度O(logn)

0 赞同 0 条回复

yanshuojune 普通 2022年11月20日上午11:19

时间复杂度：O（n），从右向左遍历，最坏情况遍历n-1次
空间复杂度：O（1）

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        L, R = 0, len(numbers) - 1
        while L < R:
            mid = L + (R - L) // 2
            # 当最小数在mid左边
            if numbers[mid] < numbers[R]:
                R = mid
            # numbers[mid] 和 numbers[R]相等时，无法判断最小数在左边还是右边（[1,3,3],[3,3,1,3]），通过R--缩小搜索范围
            elif numbers[mid] == numbers[R]:
                R -= 1
            # 最小数在mid右边
            else:
                L = mid + 1
        return numbers[L]

0 赞同 0 条回复

小肸永久会员 2022年11月15日下午3:35

思路一：顺序遍历整个数组，记录最小的元素。时间复杂度O(N)，空间复杂度O(1)。

class Solution {
    public int minArray(int[] numbers) {
        int min = numbers[0];
        for (int i = 1; i < numbers.length; i ++) {
            if (min > numbers[i]) {
                min = numbers[i];
            }
        }
        return min;
    }
}

思路二: 利用整个数组是递增的，采用二分查找的思想。比如[1,2,3,4,5]旋转3次后为4,5,1,2,3，初始时left=0，right=4，mid=2，所以numbers[right]>numbers[mid]，说明中间的元素位于第二个递增子数组。跟新right=mid，更新一次时left=0,right=2,mid=1，数组范围[4,5,1]，所以numbers[left]<numbers[mid]，说明中间的元素位于第一个的递增子数组中,更新left=mid，更新二次时left=1,right=2,mid=2，数组范围[5,1]，right-left=1，两个指针相邻，所以让mid=right=2，结束循环，返回numbers[1]。这种思路找到第一个递增子数组和第二个递增子数组的分界点。时间复杂度O(logN)，空间复杂度O(1)。

class Solution {
    public int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1;
        int mid = left; // 针对旋转0个元素的特殊情况
        while (numbers[left] >= numbers[right]) {
            if (right - left == 1) {
                mid = right;
                break;
            }
            mid = (left + right) / 2;
            // 考虑特殊情况
            if (numbers[mid] == numbers[left] && numbers[mid] == numbers[right]) {
                int minValue = numbers[left];
                for (int i = left + 1; i <= right; i ++) {
                    minValue = minValue > numbers[i] ? numbers[i] : minValue;
                }
                return minValue;
            }
            if (numbers[left] <= numbers[mid]) {
                left = mid;
            } else if (numbers[right] >= numbers[mid]) {
                right = mid;
            }
        }
        return numbers[mid];
    }
}

思路三：寻找旋转点。比如数组[3,4,5,6,7,0,1,2]，初始时left=0,right=7，mid=3,所以numbers[left]<numbers[mid]，跟新left=mid+1，更新一次时left=3,right=7,mid=5,数组范围[6,7,0,1,2]，所以numbers[left]>numbers[mid]，更新right=mid,更新二次后left=3,right=5,mid=4，数组范围[6,7,0]，所以numbers[left]<numbers[mid],更新left=mid+1，更新三次时left=4,right=5,mid=4，数组范围[7,0]，所以numbers[left]numbers[mid]，所以left=mid+1，此时leftright=5，结束循环,返回numbers[left]。时间复杂度O(logN)，空间复杂度O(1)。

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

0 赞同 0 条回复

Y7n05h 普通 2022年11月14日下午4:33

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 = (l + r) / 2;
            if(numbers[mid] > numbers[l]){
                l = mid + 1;
            }else if(numbers[mid] < numbers[l]){
                r = mid;
            }else{
                l++;
            }
        }
        return numbers[l];
    }
};

时间复杂度：O(lgN)

0 赞同 0 条回复

Whatever 永久会员 2022年11月13日下午9:23

如下：

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 = (l + r) / 2;
            if(numbers[mid] > numbers[l]){
                l = mid + 1;
            }else if(numbers[mid] < numbers[l]){
                r = mid;
            }else{
                l++;
            }
        }
        return numbers[l];
    }
}

0 赞同 0 条回复

@ 普通 2022年11月13日上午10:18

思路：二分查找
时间复杂度 O(logN）
**空间复杂度 O(1) **

//寻找最小元素即为寻找旋转点
class Solution {
    public int minArray(int[] numbers) {
        int  l = 0, r = numbers.length - 1;

       while (l < r) {
           int mid = l + (r - l) / 2;

           if(numbers[mid] > numbers[r]) 
               l = mid + 1;     //旋转点在右侧
           else if(numbers[mid] < numbers[r])
               r = mid; //旋转点在左侧
           else
                r = r - 1;  //无法确定旋转点的位置，但可以缩小范围

       }

       return numbers[l];
    }
}

0 赞同 0 条回复

黎昕普通 2022年11月12日下午10:37

二分法：
时间 O(logn) 空间 O(1)

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left,right=0,len(numbers)-1
        while left<right:
            mid=left+(right-left)//2
            if numbers[mid]>numbers[right]:
                left=mid+1
            elif numbers[mid]<numbers[right]:
                right=mid
            else:
                right-=1
        return numbers[left]

偷懒法
时间空间不清楚

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        return min(numbers)

0 赞同 0 条回复

波波_1936 普通 2022年11月11日下午9:12

    public int minArray(int[] numbers) {
        //时间复杂度O(n)//数组全相同的时候从右边遍历到左边是n
        //空间复杂度O(1)
        if (numbers == null || numbers.length == 0) return -1;
        int left = 0, right = numbers.length - 1;
        int minValue = 0;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (numbers[right] > numbers[mid]) {
                //右边有序 分界点在mid左边
                right = mid;
            } else if (numbers[right] < numbers[mid]) {
                //左边有序，分界点在mid后面
                left = mid + 1;
            } else {
                //无法二分 为了去重 从右往左遍历
                right--;
            }
        }
        return numbers[left];

    }

0 赞同 0 条回复

你有点可爱喔普通 2022年11月10日下午2:49

mid > mid+1时，数组发生了旋转，且最小值一定在mid的右侧，将左指针移动到中间值的后一位，即left = mid+1；
mid < mid+1时，还不能判断数组是否发生了旋转，所以还需要使用 mid 和 right 进行比较
mid > righ时，mid前面的元素就不需要了，最小值在mid右侧，left = mid + 1；
mid <= right时，最小值在mid左侧，也可能是mid，需要保留，即 right = mid

class Solution {
    public int minArray(int[] numbers) {
        //把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
            int left = 0,right = numbers.length-1;
            while(left<right){
                if(numbers[left]<numbers[right]){
                    return numbers[left];
                }
                int mid =(right+left)/2;
                if(numbers[mid]>numbers[left]){
                    left = mid+1;
                }else if(numbers[mid]<numbers[left]){
                    right = mid;
                }else{
                    left++;
                }
            }
            return numbers[left];
    }
}

0 赞同 0 条回复

cxc 普通 2022年11月10日上午12:10

class Solution {
    public int minArray(int[] numbers) {
        int i = 0, j = numbers.length - 1;
        while(i < j) {
            int m = (i + j)/2;
            //当 nums[m]>nums[j]nums[m] > nums[j]nums[m]>nums[j] 时： mmm 一定在 左排序数组 中，即旋转点 xxx 一定在 [m+1,j][m + 1, j][m+1,j] 闭区间内，因此执行 i=m+1i = m + 1i=m+1；
            if(numbers[m] > numbers[j]) {
                i = m + 1;
            } else if (numbers[m] < numbers[j]) {
                j = m;
            } else{
                j--;
            }
        }
        return numbers[i];
    }
}

0 赞同 0 条回复

天然普通 2022年11月10日上午12:00

看到旋转矩阵，我想到X战警-逆转未来，用反旋转的方法找到最小numbers[0],但写出来后发现不是log(n).速度太慢啦

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if len(numbers)==1: return numbers[0]
        left ,right= 0,len(numbers)-1
        while numbers[left]>=numbers[right]and left<right:
            r = numbers.pop(0)
            numbers.append(r)
            right = right-1
        return numbers[0]
#一开始是这个想法，但左右和中值关系没有想明白
class Solution:
    def minArray(self, numbers: [int]) -> int:
        i, j = 0, len(numbers) - 1
        while i < j:
            m = (i + j) // 2
            if numbers[m] > numbers[j]: i = m + 1
            elif numbers[m] < numbers[j]: j = m
            else: j -= 1
        return numbers[i]

0 赞同 0 条回复

派大星普通 2022年11月9日下午10:59

public class Solution4 {
//时间复杂度O(logn)
//空间复杂度O(1)
    public int minArray(int[] numbers) {
        if(numbers == null||numbers.length == 0)return 0;
        int l = 0,r = numbers.length - 1;
        while (l != r){
            if(numbers[l] < numbers[r]) return numbers[l];
            int m = (l + r)/2;
            if(numbers[m] > numbers[l]){
                l = m + 1;
            } else if (numbers[m] < numbers[l]) {
                r = m;
            } else{
                l++;
            }
        }
        return numbers[l];
    }
}

0 赞同 0 条回复

lobort 普通 2022年11月9日下午8:50

class Solution {
    public int minArray(int[] numbers) {
        //将数组分为左右有序的数组
        int left = 0, right = numbers.length - 1;
        //left = right 跳出
        while(left < right){
            int mid = left + ((right - left) >> 1);
            //中间数小于右边数   中间数一定在右边数组  转折点在中间数左边
            if(numbers[mid] < numbers[right]){
                right = mid ;
            //中间数大于右边数   中间数一定在左边数组  转折点在中间数右边
            }else if(numbers[mid] > numbers[right]){
                left = mid + 1;
            //中间数等于左边数时无法判断 缩小右边界
            }else{
                right--;
            }
        }
        return numbers[left];
    }
}

0 赞同 0 条回复

just 普通 2022年11月9日上午11:47

//旋转数组
class Solution {
public:
int minArray(vector& numbers) {
vector nums=numbers;
int l=0,r=nums.size()-1;
while(l<=r){
int mid=l+(r-l)/2;
if(nums[mid]>nums[r]) l=mid+1;
else if(nums[mid]>nums[r]) r=mid-1;
else r–;
}
return nums[l];
}
};

0 赞同 0 条回复

登录以回复

y 普通 2022年11月8日下午11:02

var minArray = function(numbers) {
  let l = 0;
  let r = numbers.length -1;
  while(l < r) {
      let mid = Math.floor(l + (r - l) / 2);
      if(numbers[mid] < numbers[r]) {
          r = mid;
      } else if(numbers[mid] > numbers[r]) {
          l = mid + 1;
      } else {
          r = r - 1;
      }
  }
  return numbers[l];
};

二分

0 赞同 0 条回复

T 普通 2022年11月8日下午7:13

下面代码

class Solution {
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while(low < high) {
            int mid = low + ((high - low) >> 1);
            if(numbers[mid] > numbers[high]) low = mid + 1;
            else if(numbers[mid] < numbers[high]) high = mid;
            else high--;
        }
        return numbers[low];
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月8日下午5:08

注意重复数组的处理

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

0 赞同 0 条回复

追普通 2022年11月8日下午2:30

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0, right = numbers.size() - 1;
        while(left < right){
            int mid = left + (right - left)/2;
            if(numbers[mid] > numbers[right]) left = mid + 1;  //由于mid所对应的值大于右边界的值，所以mid对应的一定不是最小数字
            else if(numbers[mid] < numbers[right]) right = mid;  //因为在该情况下，无法知道mid对应的值是否为数组的最小值，所以下一个区间仍需要将mid圈进去
            else right -= 1;
        }
        return numbers[left];
    }
};

二分法，时间复杂度为Olog(n)，空间复杂度为O(1)

0 赞同 0 条回复

优秀市民普通 2022年11月8日下午1:00

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

    }
}

旋转点就是右侧有序数组的第一个数字
时间复杂度O(log2N)

0 赞同 0 条回复

So 普通 2022年11月8日上午10:51

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 = (l + r) / 2;
            if (numbers[mid] > numbers[l]) {
                l = mid + 1;
            } else if (numbers[mid] < numbers[r]) {
                r = mid;
            } else {
                l++;
            }
        }
        return numbers[l];
    }
}

时间：O(log(n))，空间：O(1)

0 赞同 0 条回复

庄重普通 2022年11月8日上午9:25

// 思路：
//     1.理清题目：旋转一次，尾元素位置改为头部为一次旋转，因此出现多次旋转，会有x个元素旋转到数组前部，
//也会有旋转n次变为原数组的情况
//     2.首先假设该数组为旋转x次后的数组，根据旋转点（示例中为1）左边都比右边大，分情况解决使用二分查找
//     3.中间值mid比l对应的值大，说明mid处于旋转点的左边，[l,mid]的值都砍除
//     4.中间值mid比l对应的值小，说明mid处于旋转点的右边,(mid,r]的值都砍除
//     5.相等的情况，看else的注释
//     6.注意极端情况
class Solution {
public:
    int minArray(vector& numbers) {
        int l = 0 ,r = numbers.size()-1;

        int mid = 0;
        while(l < r){
            //此时为极端情况，本身还是一个升序数组
            //1.本身旋转n次之后，又变回原升序数组
            //2.在缩小范围的时候，数组突然变成升序数组，以下的二分查找思路就不适用了
            if(numbers[l] < numbers[r])
                return numbers[l];

            mid = (l + r) / 2;//向下取整
            if(numbers[mid] > numbers[l])
                l = mid + 1;
            else if(numbers[mid] < numbers[l])
                r = mid;
            else//numbers[mid] == numbers[l] ,此时出现了连续重复元素，可能出现的位置为l之后或者r的位置，直接切除l并不影响
                //整个数组还是旋转数组，不影响旋转点
                l = l+1;
        }
        return numbers[l];

    }
};
//时间复杂度O(logn)
//空间复杂度O(1)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月7日下午11:26
算法流程**

性质：左排序数组的任一元素>=右派序数组任一元素
1. 初始化：声明i，j双指针分别指向nums数组的左右两端
2. 循环二分：
  
  设mid = (i + j) / 2(恒有 i <= m < j)
  
  当nums[mid] > nums[j] 时：mid一定在左排序数组中，即旋转点x 一定在[m+1,j] 闭区间，因此执行 i = mid + 1
3. 当nums[mid] < nums[j] 时，mid一定在右派序数组中，
  
  即旋转点x一定在[i,m]区间，因此执行j = m
4. 当nums[mid] = nums[j] 时，无法判断mid到底在哪个排序数组中，即无法判断旋转点x 在[i,m]还是[m+1,j]区间中。解决方案:j = j -1 缩小判断范围
返回值：当i j跳出二分循环，并且返回旋转点的值 nums[i]即可

/*
时间复杂度o(logn)
*/
class Solution {
    public int minArray(int[] numbers) {
        int i = 0,j = numbers.length - 1;
        while(i < j){
            int mid = i + (j - i ) / 2;
            if(numbers[mid] > numbers[j]){
                //说明mid在左排序，旋转点在[mid+1,j]
                i = mid + 1;
            }else if(numbers[mid] < numbers[j]){
                //说明mid在右排序，旋转点在[i,mid]
                j = mid;
            }else if(numbers[mid] == numbers[j]){
                //无法判断，收缩范围
                //此时x也一定出现在[i,j]中
                //也可以理解为因为[mid,j]区间的元素都相等，j=j-1就是将区间减少了1个，删除的最后这个元素（下标j），在删除后的区间仍存在，所以不会删除掉旋转点x。
                j = j - 1;
            }
        }
        //i == j 时跳出循环
        return numbers[i];
    }
}

0 赞同 0 条回复

青木普通 2022年11月7日下午10:59

/**
    没想出来，还差一点T_T
     时间复杂度O(n) 最坏情况遍历一遍数组
     空间复杂度O(1)
 */
class Solution {
    public int minArray(int[] numbers) {
        int l=0, r=numbers.length-1;
        while(l < r){
            int mid = l + ((r - l) >> 1);
            if(numbers[mid] > numbers[r]){
                l = mid + 1;
            }
            else if(numbers[mid] < numbers[r]){
                r = mid;
            }
            else{
                r--;
            }
        }
        return numbers[l];
    }
}

0 赞同 0 条回复

Error 普通 2022年11月7日下午10:57

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        if numbers[0] < numbers[-1]:
            return numbers[0]
        l, r = 0, len(numbers) - 1
        while l < r:
            m = (l + r) // 2
            if numbers[m] > numbers[r]:
                l = m + 1
            elif numbers[m] < numbers[r]:
                r = m
            else:
                r -= 1
        return numbers[l]

时间 O(log n)

0 赞同 0 条回复

是梦终空永久会员 2022年11月7日下午9:06

看了下视频讲解，左边肯定比右边大（如果不是，直接返回第一个元素），然后二分，找到中间元素，左边元素小于中间元素，l = mid+1，大于的话，r=mid,相等就l++
时间O(logn)
空间O(1)

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月7日下午5:33

时间复杂度为O（lgn）空间复杂度为O（1）

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

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

共以下 33 个回答

# 回答此问题 取消回复

# 回答此问题取消回复