2017-06-07 17:20:22 +0000   |     algorithm leetcode array binary search   |   Viewed times   |    

题目

Follow up for “Find Minimum 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).

Find the minimum element.

The array may contain duplicates.

二分查找,最坏情况复杂度

代码

public class Solution {
    public int findMin(int[] nums) {
        if (nums.length == 0) { return 0; }
        int lo = 0, hi = nums.length-1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] < nums[hi]) { hi = mid; continue; } // 最小值在左半边
            if (nums[mid] > nums[hi]) { lo = mid+1; continue; } // 最小值在右半边
            if (nums[mid] == nums[hi]) { hi--; } // 有可能在左半边,也可能在右半边。只能放心丢弃最高位的元素,因为至少中位数的值和他相等。
        }
        return nums[lo];
    }
}

结果

银弹! find-minimum-in-rotated-sorted-array-two-1