无分支二进制搜索

Question

我很好奇，如果任何人都可以向我解释无分支二进制搜索实现。我在最近看到它在question中提到过，但我无法想象它将如何实施。如果项目数量非常大，我认为避免分支会很有用。

Answer 1

我打算假设你正在谈论“在你想支持的域中创建一个包含所有完美广场的static const数组，并在其上执行快速无分叉二进制搜索”。发现在this answer。

“无分支”二分查找基本上只是一个展开的二分查找循环。这只有在事先知道你正在搜索的数组中的项目数量（如果它是static const）。如果手工操作时间太长，您可以编写一个程序来编写展开的代码。

然后，您必须基准您的解决方案，看看它是否真的比循环更快。如果你的无分支代码太大，它不适合CPU的快速指令缓存，并且比等效循环花费更长的时间运行。

Answer 2

如果有一个函数根据正确项目与当前项目的位置返回+1，-1或0，可以初始化位置以列出大小/ 2，并逐步位置/ 2，并且然后在每次比较之后做位置+ =方向*步长;步长=步长/ 2。迭代到步骤为零。