algorithm - 简单范围搜索算法的伪代码

Question

我正在为即将到来的 CS 考试做一些练习题。我希望我能得到一些帮助来找出该算法的伪代码:

Given an array of n integers that have been sorted in increasing order, I need to give a pseudocode description of an algorithm to perform a range search on A having complexity O(r + logn), where r is the number of outputted points. In other words, given a closed interval [lo, hi], output all the array elements A[i] where lo <= A[i] <= hi.

---

据我所知，'r ' 复杂性的一部分将只是输出区间内的元素(将它们放置在算法中的单独数组中)。

我不太确定该怎么做。它应该只是一种算法。是否需要递归？由于算法必须是 log(n) ，不断地划分数组似乎是一个想法。我只是对如何实现它感到困惑。

Answer 1

“不断划分数组”是正确的。如果每次都除以一半，这称为“二分搜索”，实际上是 O(log(n))。

您必须执行两次搜索，一次搜索 hi，一次搜索 lo，但这不会改变复杂性的顺序，因为我们要乘以一个常数迭代次数。