¿Qué es la búsqueda binaria?

Los artículos escritos en este blog fueron creados con el objetivo de enseñar. Además, la información del artículo puede ser incorrecta, así que tenga cuidado.

La búsqueda binaria comprueba el valor medio del rango ordenado y reduce el intervalo de búsqueda a la mitad.

1 3 5 7 9 11 13
↑ 7 OK

Para encontrar 11, deja solo la mitad derecha.

implementación predeterminada

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

Dado que el rango se reduce a la mitad cada vez, la complejidad del tiempo esO(log N)soy.

debe ser ordenado

Cuando se aplica la búsqueda binaria a datos no ordenados, es imposible determinar qué mitad se puede descartar. Si ordena primero cada vez que busca, también debe calcular el costo de clasificación.

Las condiciones de contorno para el primer mismo valor, el último mismo valor y la búsqueda de la ubicación del valor son ligeramente diferentes. En C++std::lower_boundystd::upper_boundPuede obtener este límite de forma segura utilizando .

La parte difícil de la búsqueda binaria es no encontrar el valor medio. Ya sea que el rango actual sea un tramo cerrado o un tramo semiabierto, la misma regla se mantiene hasta el final.