带子数组打印的递归二分查找时间复杂度分析及疑问

打印部分的时间复杂度 #

打印部分的时间复杂度是O(n)。

最坏情况下（比如查询值x比数组所有元素大/小且最终未找到），每次递归会打印当前子数组的一半元素，再进入另一半递归。例如：当x大于所有元素时，第一次打印右半部分（约n/2个元素），第二次打印新子数组的右半部分（约n/4个元素），依此类推直到子数组长度为1。所有打印元素的总数是等比数列求和：n/2 + n/4 + n/8 + ... + 1，总和趋近于n，因此打印操作的总时间复杂度为O(n)。

代码总运行时间 #

总运行时间是O(n)。

递归部分的时间复杂度为O(logn)，但这部分仅包含计算中间索引、条件判断等O(1)级别的操作，总耗时远小于打印部分的O(n)。在大O表示法中，整体复杂度由主导项决定，因此总运行时间由打印部分的O(n)主导。

递归部分对总运行时间的影响 #

递归部分的O(logn)不会影响总运行时间。因为O(n)的量级远大于O(logn)，在大O复杂度分析中，更小量级的项会被忽略，最终总复杂度由O(n)决定。

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