Find Minimum in Rotated Sorted Array II
Question
- leetcode: Find Minimum in Rotated Sorted Array II | LeetCode OJ
- lintcode: (160) Find Minimum in Rotated Sorted Array II
Problem Statement
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.
Example
Given [4,4,5,6,7,0,1,2] return 0
题解
由于此题输入可能有重复元素,因此在num[mid] == num[end]
时无法使用二分的方法缩小start或者end的取值范围。此时只能使用递增start/递减end逐步缩小范围。
C++
1 | class Solution { |
Java
1 | public class Solution { |
源码分析
注意num[mid] > num[ub]
时应递减 ub 或者递增 lb.
复杂度分析
最坏情况下 \[O(n)\], 平均情况下 \[O(\log n)\].
Find Minimum in Rotated Sorted Array II