Finding on item in a circular queue?

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.

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.

By definition I don't think a queue should allow to access its members by index.. – Umair Ahmed Jun 5 '09 at 13:45 A circular queue does allow access via index (since it's a simple array) but the start and the end of the queue rotate which makes binary search more difficult (not impossible). The sort of situations where you use circular queues usually makes binary searches unnecessary (they're usually reasonably small). – paxdiablo Jun 5 '09 at 13:49.

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 elementptr = searchvalue: return true if elementptr > searchvalue: return false ptr = (ptr + 1) % queuesize; return false.

– AnthonyWJones Jun 5 '09 at 13:39 @Anthony, a LIFO is any structure that does last-in-first-out of which a unidirectional circular queue is one type. – paxdiablo Jun 5 '09 at 13:46.

Ie from tail to head. If so then we can design something that can utilize URL1 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.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.