什麼是二分查找？

該部落格上撰寫的文章是出於教學目的而創建的。 另外，文章中的資訊可能不正確，請謹慎。

二分查找檢查排序範圍的中間值，並將搜尋間隔減少一半。

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您可以使用 安全地取得此邊界。

二分查找的困難在於找不到中間值。 無論目前區間是封閉區間還是半開放區間，都保持相同的規則直到結束。