153. Find Minimum in Rotated Sorted Array

发表于 | 分类于 | 阅读次数

Description

使用二分查找的两道题，包括了二分查找原理即题型汇总。

  1. Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
    (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
    Find the minimum element.
    You may assume no duplicate exists in the array.

  2. Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
    (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
    Find the minimum element.
    The array may contain duplicates.

我就说怎么这么熟悉呢， 见[leetcode81]Search in Rotated Sorted Array II.

Solution

第1题，第2题这种题目放出来，必然是要用比较优的方法来解决了，对于这种可以看做是有序序列的查找问题一般就是用二分查找来解决，这里也会总结所有二分查找的题目。

二分查找原理

算法第4版P15中提到
第一步：接收给定的有序序列
第二步：取其中间的数与给定数判断，如果给定数小于中间的数，将序列的左半部分传给第一步；如果给定数大于中间的数，将序列的右半部分传给第一步；否则返回中间数的下标
其中mid的求解是left+(right-left)/2，因此对于偶数列，中间取左边

1
2
3
4
5
6
7
8
9
10
11
#二分查找
def rank(key,a,left,right):
    if left>right:
        return -1
    mid=left+(right-left)/2
    if a[mid]<key:
        return rank(key,a,mid+1,right)
    elif a[mid]>key:
        return rank(key,a,left,mid-1)
    else:
        return mid

[leetcode 153]Find Minimum in Rotated Sorted Array

没有重复的元素，不会涉及到相等的问题，这道题的思路就是，如果中间的数大于数组头元素，那么桌板部分最小值必然是数组头元素，继续判断右半部分即可；如果中间的数小于数组头元素，那么右边的最小值一定是中间的数，继续判断左半部分即可。代码写的有点啰嗦，可以优化的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findMin(int[] nums) {
    if(nums==null||nums.length==0)return -1;
    if(nums.length==1)return nums[0];
    int start,middle,end;
    int res;
    start=0;
    end=nums.length-1;
    middle=0;
    res=Integer.MAX_VALUE;
    while (start<=end){
        middle=(start+end)/2;
        if(nums[middle]>nums[start]||middle==start){
            res=Math.min(res,nums[start]);
            start=middle+1;
        }else{
            res=Math.min(res,nums[middle]);
            end=middle-1;
        }
    }
    return res;
}

[leetcode 154]Find Minimum in Rotated Sorted Array II

出现了重复的元素，这样就需要考虑重复的情况。
思路：中间的数和最后面的数相比，如果中间的数大于最后面的数，说明最小值在中间数的下一个元素到最后元素之间，那么让start指针指向中间数的下一个数；如果中间的数小于最后面的数，那么右半部分最小值必然是中间的数，即整个数组的最小值必然在最前面的数到中间的数之间，start不用变，只用将end向前移到mid指针处即可；如果中间的数等于最后面的数，这时只需要将最后面的数前移即可【这里出现的两种情况（[3,4,3,3,3],[3,3,3,2,3]）】。注意返回的是最前面的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findMin(int[] nums) {
    if(nums==null||nums.length==0)return -1;
    int start,mid,end;
    start=0;
    end=nums.length-1;
    mid=0;
    while (start<end){
        mid=(start+end)/2;
        if(nums[mid]<nums[end])end=mid;
        else if(nums[mid]>nums[end])start=mid+1;
        else end--;
    }
    return nums[start];
}

[leetcode 69]Sqrt(x)

Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
这道题严格要求时间复杂度为O(lgn)，所以一般的遍历是无法解决的。思路是，从0到x中选取一个数mid，使得mid满足，然后用二分查找进行查找即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int mySqrt(int x) {
    if(x==0) return 0;
    int left=1;
    int right=x;
    int mid;
    while (true){
        mid=(left+right)/2;
        if(mid*mid>x){
            right=mid-1;
        }else {
            if((mid+1)*(mid+1)>x)return mid;
            left=mid+1;
        }
    }
}

[leetcode 81]Search in Rotated Sorted Array II

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
这道题目和前面的完全一样，前面的题目是要找最小值，这里是要找目标值，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public boolean search(int[] nums, int target) {
    if(nums==null||nums.length==0)return false;
    int left,right,middle;
    left=0;
    right=nums.length-1;
    while (left<=right){
        middle=(left+right)/2;
        if(nums[middle]==target)return true;
        //满足条件说明left-middle之间是有顺序的
        if(nums[middle]>nums[left]){
            //如果位于左半部分
            if(target>=nums[left]&&nums[middle]>=target){
                right=middle-1;
            }else {
                left=middle+1;
            }
        }
        //右边有序
        else if(nums[middle]<nums[left]){
            //如果位于右边
            if(target<=nums[right]&&target>=nums[middle]){
                left=middle+1;
            }else {
                right=middle-1;
            }
        }
        //无法区分，需要向前进，找到不相等的值
        else {
            left++;
        }
    }
    return false;
}

长期更新！

如果觉得有帮助，给我打赏吧！