分块有序数组元素查找算法的时间复杂度咨询

你的思路完全没问题，不需要更换方案。这个改进思路精准利用了分区之间的有序性来快速缩小查找范围，比直接遍历整个数组的效率更高。

时间复杂度分析 #

你给出的两个选项都不准确，正确的时间复杂度是 O(log(n/k) + k)：

• 二分查找定位分区：数组被划分为 n/k 个分区，二分查找的时间复杂度为 O(log(n/k))
• 遍历目标分区：每个分区固定有 k 个元素，遍历操作的时间复杂度为 O(k)
• 两者相加就是总时间复杂度，既不是 O(k*log(n/k))（这是错误地把两个步骤的复杂度相乘了），也不是单纯的 O(k)（忽略了二分查找的开销，只有当 n/k 是常数时，log(n/k) 才会退化为常数项）

举个实际例子：当 n=100、k=10 时，分区总数是10，二分查找最多4次就能锁定目标分区，再遍历10个元素，总操作量远小于直接遍历100个元素的开销。

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