無分支二進制搜索

Question

我很好奇，如果任何人都可以向我解釋無分支二進制搜索實現。我在最近看到它在question中提到過，但我無法想象它將如何實施。如果項目數量非常大，我認爲避免分支會很有用。

Answer 1

我打算假設你正在談論「在你想支持的域中創建一個包含所有完美廣場的static const數組，並在其上執行快速無分叉二進制搜索」。發現在this answer。

「無分支」二分查找基本上只是一個展開的二分查找循環。這隻有在事先知道你正在搜索的數組中的項目數量（如果它是static const）。如果手工操作時間太長，您可以編寫一個程序來編寫展開的代碼。

然後，您必須基準您的解決方案，看看它是否真的比循環更快。如果你的無分支代碼太大，它不適合CPU的快速指令緩存，並且比等效循環花費更長的時間運行。

Answer 2

如果有一個函數根據正確項目與當前項目的位置返回+1，-1或0，可以初始化位置以列出大小/ 2，並逐步位置/ 2，並且然後在每次比較之後做位置+ =方向*步長;步長=步長/ 2。迭代到步驟爲零。