Search code examples
algorithmsearchrangepseudocode

Pseudocode for simple range search algorithm

I am working through some practise problem sets for an upcoming CS exam. I was hoping I could get some help figuring out pseudocode for this algorithm:

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.

I understand that the 'r' portion of the complexity will simply be outputting the elements which are within the interval (having placed them in a separate array in the algorithm).

I am not quite sure how to do this. It is suppose to be just one algorithm. Is recursion necessary? Since the algorithm has to be log(n), dividing the array constantly seems like an idea. I am just confused on how to implement it.

Solution

  • "Dividing the array constantly" is correct. If you do this by dividing in half every time, this is called a "binary search", which is indeed O(log(n)).

    You will have to do the search twice, once for hi and once for lo but that does not change the order of complexity, since we are multiplying by a constant number of iterations.