旋转有序数组查找元素算法的时间复杂度是否为(log n)²？

好的，咱们来一步步拆解这个问题，看看你的分析哪里有偏差，以及这段代码实际的时间复杂度是多少。

问题：给定一个经过未知次数旋转的升序数组，编写代码查找某个元素。现在分析这段代码的时间复杂度，我认为是*(log n)²*，因为每个findindex函数的递归深度为logn，且我们调用了它logn次？希望有人帮忙确认。

代码回顾 #

# Ex # input find 5 in {15,16,19,20,25,1,3,4,5,7,10,14} # output 8 # runtime(log n)
def findrotation(a, tgt):
    return findindex(a, 0, len(a)-1, tgt, 0)
def findindex(a, low, high, target, index):
    if low>high:
        return -1
    mid = int((high + low) / 2)
    if a[mid] == target:
        index = index + mid
        return index
    else:
        b = a[low:mid]
        result = findindex(b, 0, len(b)-1, target, index)
        if result == -1:
            index = index + mid + 1
            c = a[mid+1:]
            return findindex(c, 0, len(c)-1, target, index)
        else:
            return result

你的分析误区 #

你认为复杂度是*(log n)²*，核心偏差在于对递归调用次数的判断——这段代码在最坏情况下的调用次数远不止logn次，递归逻辑也不是“调用logn次、每次深度logn”的模式。

实际时间复杂度推导 #

我们从递归逻辑入手拆解：
每次调用findindex处理长度为n的数组时：

• 若中间元素不是目标，会先递归遍历左半部分（长度约n/2）；
• 如果左半没找到目标，再递归遍历右半部分（长度约n/2）。

最坏情况下（比如目标在数组最右端，且每次左半都找不到），每个findindex调用都会触发两次子递归。用递推式表示：

• 基准情况：T(1) = O(1)（直接判断唯一元素）
• 递推式：T(n) = T(n/2) + T(n/2) + O(1)（左半递归+右半递归+常数时间判断）

根据主定理（Master Theorem），这里a=2（每次生成2个子问题），b=2（子问题规模是原问题的1/2），f(n)=O(1)。因为log_b a = 1，且f(n) = O(n^0) < n^1，所以时间复杂度为O(n)。

另外还要注意：代码里的数组切片（a[low:mid]、a[mid+1:]）本身是O(k)复杂度（k为切片长度），这会让实际运行的常数项更高，但整体量级还是O(n)。

为什么你的假设不成立？ #

你以为调用findindex的次数是logn次，但实际上最坏情况下调用次数是指数级增长的：

• 处理n长度数组，会调用2次n/2长度的；
• 每个n/2长度的又会调用2次n/4长度的，以此类推；
• 总调用次数是1 + 2 + 4 + ... + n = 2n-1，也就是O(n)次，远大于logn次。

额外补充：如何优化到O(logn)？ #

如果想要达到题目注释里标注的runtime(log n)，不能用这种暴力切分递归的方式，要利用旋转数组的特性：数组的某一半一定是有序的。优化思路如下：

1. 找到中间元素，判断左半部分是否有序；
2. 如果左半有序，且目标在左半的区间内，就只递归左半；否则递归右半；
3. 如果左半无序，那右半一定有序，同理判断目标是否在右半区间内，选择单一递归方向。

内容的提问来源于stack exchange，提问作者Matt Choi