二進制搜索與最後一次匹配的最接近的匹配

我正在實現有效的算法來搜索（密鑰或最近的匹配（上限））的最後一次出現。二進制搜索與最後一次匹配的最接近的匹配

到目前爲止，我得到了這一點。

long bin_search_closest_match_last_occurance (long * lArray, long sizeArray, long lnumber) 
{ 
    long left, right, mid, last_occur; 

    left = 0; 
    right = sizeArray - 1; 
    last_occur = -1; 

    while (left <= right) 
    { 
     mid = (left + right)/2; 

     if (lArray[mid] == lnumber ) 
     { 
      last_occur = mid; 
      left = mid +1; 
     } 

     if (lArray[mid] > lnumber) 
      right = mid - 1; 
     else 
      left = mid + 1; 
    } 
    return last_occur!=-1?last_occur:mid; 
}

讓我們有一個數組{0,0,1,5,9,9,9,9}關鍵是6 FCE應該返回指數7，但我的FCE返回4

請注意，我不想線性迭代到最後的匹配指標。

記住我有我更改參數fce（添加開始，結束索引）的解決方案，並執行另一個二進制搜索fce從發現的上限到數組的末尾（只有當我找不到完全匹配時，last_occur==-1）。

我想問問有沒有更好/更簡潔的方案來實現它？

來源

2014-11-25 Rob

不知道爲什麼它應該返回7.它要求找到鑰匙，或最近比賽的最後一次出現，因此，如果關鍵不在列表中（這是你的例子） - 返回4應該沒問題，因爲我理解任務描述。 – amit 2014-11-25 11:36:40

@amit編輯了這個問題。現在應該更清楚了 – Rob 2014-11-25 11:41:49

你打開一個{在你的while指令之後，你永遠不會關閉它。 – 2014-11-25 11:44:56

納米的2-搜索方法將工作，並保持最佳的時間複雜度，但它可能是由約2至增加常數因子，或約1.5，如果你開始從第一次搜索結束，其中第二搜索。

相反，如果你採取的發現lnumber的第一實例（或者，如果它不存在，下限），並改變它，這樣的算法邏輯「反轉」的「普通」的二進制搜索陣列，通過改變每一個數組訪問lArray[x]lArray[sizeArray - 1 - x]到（對於任何表達x），並且還通過改變> lnumber測試< lnumber「反向」的排序，則需要只有一個單一的二進制搜索。唯一的數組訪問這個算法實際執行兩種查找到lArray[mid]，其中優化的編譯器很可能只計算一次，如果能證明，沒有什麼會改變訪問之間的值（這可能需要增加restrict到long * lArray聲明;或者，您可以將該元素加載到局部變量中，然後測試兩次）。無論哪種方式，如果只需要每次迭代一個數組查找，然後改變從mid到sizeArray - 1 - mid指數將增加每次迭代只需2個額外的減法（或只有1，如果你--sizeArray進入循環前），我預計不會增加幾乎和納米的方法一樣。當然，就像任何事情一樣，如果性能很關鍵，那就測試一下;如果不是，那麼不要太在意節省微秒。

您還需要「反向」的返回值過：

return last_occur!=-1?last_occur:sizeArray - 1 - mid;

來源

2014-11-25 14:26:05

二進制搜索與最後一次匹配的最接近的匹配

回答

相關問題