Finding an item in a circular queue?

Question

I have a circular queue of ordered items. I want to know if an item with the value of "x" is in it.

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

Answer 1

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.