排序整數列表中的近似搜索算法

Question

考慮一個整數數組（假定爲排序）;我想以最快的方式找到最接近給定整數的整數的數組索引。而在存在多種可能性的情況下，該算法應該識別所有。例如：考慮T =（3,5,24,65,67,87,129,147,166），並且如果給定的整數是144，那麼代碼應該將147標識爲最接近的整數，並且給出數組索引7對應於該條目。對於66的情況，算法應該識別65和67.

是否有O（1）或至少O（log N）算法來做到這一點？直接搜索算法（二進制搜索，樹搜索，散列等）實現將不起作用，因爲那些將需要完美匹配。有什麼辦法可以修改這些以處理大致的搜索？

我正在開發一個C代碼。

謝謝

Answer 1

做二分搜索，直到你找到一個單一的元素。 如果有匹配，請沿着鄰居散步以尋找其他匹配。 如果沒有匹配，請查看您的直接鄰居以找到最接近的匹配項。

Answer 2

正確實施binary-search應該做的伎倆 - 只要你確定你的搜索範圍只減少到兩個項目的時刻。然後，您只需選擇最近的那個。複雜性：O（log n）。