剑指 offer set 3 旋转数组的最小数字

总结

1. 没有重复元素的旋转数组可用 logn 时间内求出结果. 解法有两个步骤, 先是求出发生旋转的点(以 array[0] 为支点求得), 然后用正常的二分查找给出结果

2. 有重复元素元素的旋转数组时间复杂度最差会是 o(n). 讨论下复杂度上升的原因

对于没有重复的旋转数组

4  5  6  1  2  3

pivot = 4

mid = num[2] (5) 

mid > pivot ==> 旋转点在 num 右边

以此为根据找到支点

而假如旋转数组有重复元素, 比如

1  0  1  1  1

pivot = 1

mid = num[2] = 1

mid == pivot ==> 无法进行二分了, 只能顺序遍历, 时间复杂度上升到 o(n)

剑指 offer set 3 旋转数组的最小数字

原文：http://www.cnblogs.com/xinsheng/p/3561478.html