总结
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)