Finding on item in a circular queue?

Question

I have a circular queue of ordered items.

How to find whether or not an item with the value of x is in it?

What is the best way (algorithm) to do this?

Answer 1

"Best" is a subjective term and circular queues are rarely large enough to warrant binary searches so I'd opt for simplicity in the absence of information regarding queue size. The easiest way is just to start at the head and check each element until the tail (or you've passed beyond it in the order) to see if it exists.

Let's say your head variable points to the first item that will be removed and the tail points to the next place to put an item. Further assume that you're wasting an item slot to simplify the code (a trick to simplify the code and tell the difference between an empty and full queue). That means and empty queue is indicated by tail == head.

ptr = head
while ptr != tail:
    if element[ptr] = searchvalue:
        return true
    if element[ptr] > searchvalue:
        return false
    ptr = (ptr + 1) % queuesize;
return false

Answer 2

If you can access each item by index, you can use a binary search.

If you can only see the first item, you need to pop them from the queue until the search key is lower than the key of the item you just popped. Since the queue is sorted, you can stop as soon as you know that the key can't be in the queue anymore.

[EDIT] Since you can access by index: Warp the circular queue in an object which maps it to an "array" (i.e. with a method get(index) where index runs from 0 to length-1 and which internally does ((index+start)%length).

That way, you can apply the binary search without thinking about the actual data layout.

Answer 3

can we traverse in the opposite direction? ie from tail to head. if so then we can design something that can utilize it. ie decide which way to proceed the search.

Since it is ordered we can guess about its position (just a guess or perhaps utilize statistics if available) and then start the full search only in direction which would get the result in less pulls