题目：

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

public class Solution {
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while(l < r){
            int m = l + (r - l) / 2;
            if(nums[m] > nums[r]) l = m + 1;
            else if (nums[m] < nums[r]) r = m;
            else r--;
        }
        return nums[l];
    }
}