讨论/《二分查找》 - 寻找旋转排序数组中的最小值/
《二分查找》 - 寻找旋转排序数组中的最小值
共 13 个回复

思路清晰

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=0,r=nums.size()-1,mid;
        while(l<r){
            mid=l+(r-l)/2;
            if(nums[l]<=nums[r])  //已经成为递减数组
                return nums[l];
            else if(nums[mid]>=nums[l]) //mid落在左边有序数组,则左边界一定右移
                l=mid+1;
            else
                r=mid;
        }
        return nums[l];
    }
};
2

旋转点在数组中的下标+1就是旋转的次数
不断判断当前值mid与旋转点的位置关系,之后向旋转点的那边二分

static int findMin(int[] nums) {
		int left=0,right=nums.length-1,mid=0;
		while(left<right) {
		mid=left+(right-left)/2;
		if(nums[mid]<nums[right]){
//首先判断旋转点与当前值的位置,若nums[mid]>nums[right]则旋转点在当前值右边,否则左边
		if(nums[mid]<=nums[mid+1])
			right=mid;
		}else {
			left=mid+1;
		}
		}
		return nums[left];		
    }
1

JAVA

执行用时:0 ms, 在所有 Java 提交中击败了100.00%

内存消耗:37.8 MB, 在所有 Java 提交中击败了72.19%的用户

思路: Knuth曾说过,二分法“思路简单,细节魔鬼”。比如说目标值的判断、边界的更新。我在这只分享一下我的解题思路,欢迎大家指正,一起探讨问题。
题目需要找的目标值是数组中最小的数,仔细观察发现,旋转点的值就是最小值。假设数组为[A1,A2,……,Ak,……,An]Ak为旋转点。则每次二分都要判断当前值与Ak的关系。如果是当前值在旋转点左边,则缩小左边界;如果当前值在旋转点右边,则缩小右边界;如果当前值就是旋转点,则返回。至于如何判断当前值与旋转点的位置关系,见代码注释

class Solution {
    public int findMin(int[] nums) {
        
        int size = nums.length;
        int head = 0;
        int tail = size - 1;

        while (head <= tail) {
            int mid = head + (tail - head) / 2;
            int hv = nums[head];
            int mv = nums[mid];
            int tv = nums[tail];

            // 判断当前值与旋转点的位置,并返回结果或更新边界
            if (mv > tv) {  
                //如果当前值大于右边界,则当前值必定在旋转点右边
                head = mid + 1;
            } else if (mid == 0 || mv < nums[mid - 1]) { 
                //如果当前值不在旋转点右边,则判断当前值是否大于当前值左边元素的值,如果大于则当前值为旋转点。
                return mv;
            } else { 
                //如果当前值既不在旋转点右边,也不是旋转点,则必然在旋转点左边
                tail = mid - 1;
            }
        }
        return nums[head];
    }
}
1

C++

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        while(left<right)
        {
            int mid=(left+right)/2;
            if(nums[left]<=nums[mid])
                if(nums[mid]>nums[right])
                    left=mid+1;
                else
                    return nums[left];
            else
                right=mid;  
        }
        return nums[left];
    }
};
1
class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[-1]: lo = mid + 1
            else: hi = mid
        return nums[lo]
1
class Solution {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            } else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
}

c++ 遇到旋转数组要分类讨论。
讨论翻折点在mid前,在mid后的两种情况。
再从两种情况里二分。

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return 0;
        int left=0;
        int right=nums.size()-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]>nums[0]){
                if(nums[mid]>nums[nums.size()-1]){
                    left=mid+1;
                }else{
                    right=mid;
                }
            }else{
                if(nums[mid]<nums[nums.size()-1]){
                    right=mid;
                }else{
                    left=mid+1;
                }
            }
        }
        return nums[left];
    }
};

java

class Solution {
    public int findMin(int[] nums) {
        if(nums.length==1)  return nums[0];
        int l=0,r=nums.length-1,mid;
        while(l<r){
            mid=(l+r)>>1;
            if(nums[l]<nums[r]){
                return nums[l];
            }
            else if(nums[l]>nums[mid]){
                r=mid;
            }
            else l=mid+1;
        }
        return nums[l];
    }
}
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {   
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
};

为什么我完全想不通,大于号,小于号的问题?还有要不要 + 1 的问题?