题目描述

现有一个有序数组，假设从某个数开始将它后面的数按顺序放到了数组前面。
(即 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2])。

请找出数组中的最小元素。

数组中可能包含重复元素。

样例

输入：[1,3,5]
输出：1

样例

输入：[2,2,2,0,1]
输出：0

算法1

(二分)

153题：没有重复元素
因此，利用性质：min之前的数 $a[i]>=a[0]$；之后的数都不满足这个条件，可以每次去掉一半，二分出所有的值，时间复杂度是o(lgn)

154题：有重复元素 且 rotated array -> 分析时间复杂度
1、如果单考察求min，遍历一遍，时间复杂度为 o(n)，即可
2、如果有rotated 且 重复的性质就有 值得讨论的case： 2, 2, 2, 2, 3, 1, 2;
则不能确定哪个是最小值，
解法：
a[mid] > a[r], mid 一定不是最小值，且 [l,mid]单调递增（是rotated的), l = mid + 1
a[mid] < a[r], mid 可能是最小值，[r, mid] 单调递增（是rotated的)，r = mid
a[mid] == a[r], 不确定，两边都有可能，r–

时间复杂度

best:$O(lgn)$, worst：$o(n)$

参考文献

Java 代码

 public int findMin(int[] a) {
        int l = 0;
        int r = a.length - 1;

        while(l < r) { // 注意这里没有变
            int mid = (l + r) >> 1;
            if (a[mid] > a[r]) l = mid + 1;
            else if (a[mid] < a[r]) r = mid;
            else r--;
        }
        return a[l];
    }