queue - 在循环队列中查找项目？

Question

我有一个已订购商品的循环队列。我想知道其中是否有值为“x”的项目。

执行此操作的最佳方法(算法)是什么？

Answer 1

如果您可以通过索引访问每个项目，则可以使用二分查找。

如果只能看到第一项，则需要将它们从队列中弹出，直到搜索键低于刚刚弹出的项的键为止。由于队列已排序，您可以在知道 key 不再位于队列中时立即停止。

[编辑] 因为你可以通过索引访问:将循环队列映射到一个对象中，并将其映射到一个“数组”(即使用方法 get(index) where index 从 0 到 length-1 并且在内部执行 ((index+start)%length)。

这样，您就可以在不考虑实际数据布局的情况下应用二分查找。