Leetcode 153. Find Minimum in Rotated Sorted Array（分治和二分）

Leetcode 153. Find Minimum in Rotated Sorted Array

题目链接： Find Minimum in Rotated Sorted Array

难度：Medium

题目大意：

将一个严格升序的数组循环移位若干次，求这个数组的最小元素。时间复杂度要求

O（logn）

。

思路1：

分治，找出乱序出现的位置即可找到最小值。

代码

class Solution {
    public int findMin(int[] nums) {
        int n=nums.length;
        int index=binarySearch(nums,0,n-1);
        if(index!=-1){
            return nums[index+1]; 
        }
        return nums[0];
    }
    public int binarySearch(int[] nums, int l,int r){
        //寻找index使得nums[index]>nums[index+1]
        if(l==r){
            return -1;
        }
        int mid=(l+r)/2;
        if(mid+1<=r&&nums[mid]>nums[mid+1]){
            return mid;
        }
        int left=binarySearch(nums,l,mid);
        int right=binarySearch(nums,mid+1,r);
        if(left>=l&&left<mid){
            return left;
        }
        if(right>=mid+1&&right<r){
            return right;
        }
        return -1;
    }
}
           

思路2：

二分法。

代码

class Solution {
    public int findMin(int[] nums) {
        int n=nums.length;
        int l=0,r=n-1;
        while(l<r){
            if(nums[l]<nums[r]){
                return nums[l];
            }
            int mid=l+(r-l)/2;
            if(nums[mid]>=nums[l]){//需要加等号，比如[2,1]
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        return nums[l];
    }
}