What is binary search?

The articles written on this blog were created with the goal of teaching. Also, the information in the article may be incorrect, so please be careful.

Binary Search checks the middle value of the sorted range and reduces the search interval by half.

1 3 5 7 9 11 13
↑ 7 OK

To find 11, leave only the right half.

default implementation

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;
}

Since the range is halved each time, the time complexity isO(log N)am.

Must be sorted

When binary search is applied to unsorted data, it is impossible to determine which half can be discarded. If you sort first every time you search, you must also calculate the cost of sorting.

The boundary conditions for the first same value, last same value, and finding the location of the value are slightly different. In C++std::lower_boundandstd::upper_boundYou can safely obtain this boundary by using .

The difficult part of binary search is not finding the middle value. Whether the current range is a closed section or a semi-open section, the same rule is maintained until the end.