查找循環隊列中的項目？

Question

我有一個訂購物品的循環隊列。我想知道是否有一個值爲「x」的項目在其中。

要做到這一點，最好的方法（算法）是什麼？

Answer 1

如果您可以按索引訪問每個項目，則可以使用二分查找。

如果您只能看到第一個項目，您需要從隊列中彈出它們，直到搜索鍵低於剛剛彈出的項目的鍵。由於隊列已排序，只要知道密鑰不再在隊列中，就可以立即停止。

[編輯]由於可以通過索引來訪問：經紗在其中它映射到一個「陣列」（即，具有方法的對象的圓形隊列get(index)其中index運行從0到length-1的且在內部確實((index+start)%length)

。

這樣的話，你可以從尾部到頭部應用二進制搜索，而不考慮實際的數據佈局。

Answer 2

「最好」是一個主觀術語，循環隊列很少大到足以保證二進制搜索，所以我會選擇在沒有關於隊列大小的信息時簡單。最簡單的方法是從頭部開始，檢查每個元素，直到尾部（或者你已經按順序超越了它）來查看它是否存在。

假設您的頭部變量指向將被移除的第一個項目並且尾部指向放置項目的下一個位置。進一步假設你正在浪費一個物品槽來簡化代碼（這是一種簡化代碼並告訴空白隊列和完整隊列之間差異的技巧）。這意味着空隊列由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 3

我們可以向相反的方向穿越？也就是說，如果這樣的話，我們可以設計一些可以利用它。即決定進行搜索的方式。

由於它是有序的，我們可以猜測它的位置（只是一個猜測，或者可能利用統計數據），然後開始全面搜索，只在方向上得到更少的結果