什么是二分查找？

该博客上撰写的文章是出于教学目的而创建的。 另外，文章中的信息可能不正确，请谨慎。

二分查找检查排序范围的中间值，并将搜索间隔减少一半。

1 3 5 7 9 11 13
↑ 7 好

要找到 11，只留下右半部分。

默认实现

int BinarySearch(const std::vector<int>& Values, int Target)
{
    int Left = 0;
    int Right = static_cast<int>(Values.size()) - 1;

    while (Left <= Right)
    {
        const int Middle = Left + (Right - Left) / 2;

        if (Values[Middle] == Target)
        {
            return Middle;
        }

        if (Values[Middle] < Target)
        {
            Left = Middle + 1;
        }
        else
        {
            Right = Middle - 1;
        }
    }

    return -1;
}

由于每次范围减半，时间复​​杂度为O(log N)是。

必须排序

当二分查找应用于未排序的数据时，无法确定哪一半可以被丢弃。 如果每次搜索都先排序，还必须计算排序的成本。

第一个相同值、最后一个相同值以及查找该值的位置的边界条件略有不同。 在 C++ 中std::lower_bound和std::upper_bound您可以使用 安全地获取此边界。

二分查找的难点在于找不到中间值。 无论当前区间是封闭区间还是半开放区间，都保持相同的规则直到结束。