对有序数组先二分查找再线性搜索的运行时间复杂度是多少？

你之前的时间复杂度估算存在误差，该range方法的实际时间复杂度为 O(log n + k)，其中k为符合查询范围的Key总数量。

具体拆解逻辑： #

• 第一步用二分查找定位起始符合要求的元素，这部分的时间复杂度确实是O(log n)，该环节的判断没有问题。
• 后续线性搜索遍历到最后一个符合要求的元素的环节，耗时完全和范围内的元素总数k挂钩：极端场景下如果所有元素都落在你的查询范围内，k就等于总元素数n，此时整个方法的时间复杂度会直接退化为O(n)，这就是运行耗时远高于你预期的核心原因。

优化建议： #

如果要降低查询环节的时间复杂度，可以再增加一次二分查找定位到结束Key的对应位置，直接截取两个位置之间的元素即可，无需线性遍历，这样查询阶段的时间复杂度可以稳定在O(log n)。需要注意的是，最终要返回k个元素的话，复制结果的开销O(k)是无法避免的，属于输出结果的必要成本。

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