LeetCode #154 Find Minimum in Rotated Sorted Array II

题目:

Suppose a sorted array 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.

 

分析:

一个升序数组(可能有重复元素),所有元素旋转n个位置,例如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]。但是你不知道n是多少。请找出旋转后的数组中的最小元素。

下面给出一个二分查找的解法。在数列中,最小的数有一个特征:该数左侧的所有数都大于等于右侧的数,并且左侧和右侧的数都分别是递增的。开始,使用2个指针l,r指向数组的两端。根据刚才提到的特征,为了使l和r不断逼近最小的数,l应当尽可能指向更大的数,r应当尽可能指向更小的数。比较r和中间的数m。如果m较小,则r指向m;如果r较小,则l指向m+1。由于数组中可能出现相同的元素,如果m和r相等怎么办?只要把r左移一位再继续查找即可。

另外说明一下,取中间数的时候为什么用 m = l + (r – l) / 2 而不是 m = (l + r) / 2。如果数组的长度太大,以至于大于等于int的上界,l + r可能会引起溢出而变成负数。所以我们分成2步,先做减法,再做加法,防止溢出。

 

代码:

Java