c++ - 如何对任意排序的数据执行（几乎）无分支二进制搜索？

Question

如何以最好的可移植方式对任意排序数组执行（几乎）无分支二进制搜索？（例如，帮助编译器生成 CMOV 指令的代码对此非常有用。）

“几乎”是指“包含尽可能少的分支”。

Answer 1

这是我用 Visual C++ 2012（64 位）测试时std::lower_bound只有一个分支（即测试）的版本：begin != end

template<class FwdIt, class T, class P>
FwdIt branchless_lower_bound(FwdIt begin, FwdIt end, T const &val, P pred)
{
    while (begin != end)
    {
        FwdIt middle(begin);
        std::advance(middle, std::distance(begin, end) >> 1);
        FwdIt middle_plus_one(middle);
        ++middle_plus_one;
        bool const b = pred(*middle, val);
        begin = b ? middle_plus_one : begin;
        end = b ? end : middle;
    }
    return begin;
}

支持 SSE2 的 32 位也可能能够使用 Conditional-Move 指令来获得类似的速度。

现在速度应该可以与小型阵列的线性搜索相媲美......但它可能值得检查。

---

有趣的是，我发现对于vector<int>我的 CPU 上最大（大约）45 的大小，线性搜索仍然更快！不知道为什么，或者我的测量是否准确......

---

事实证明，这并不比我的 i5 CPU 上的分支二进制搜索快。