CODEWITHSUNDEEP
algorithmsearchrangepseudocode
Tesla
Tesla

Reputation: 822

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.

Upvotes: 2

Views: 3720

Answers (2)

John Gietzen
John Gietzen

Reputation: 49575

"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.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 373482

As a hint, think about how you might adapt the binary search algorithm to find the first element greater than or equal to lo and the last element less than or equal to hi. How long would each search take? And how would you modify binary search in this fashion?

Upvotes: 2

Related Questions