Búsqueda Binaria (receta)

binary_search.cpp

// Asumiento que quiero hacer una búsqueda binaria en el rango [0, n)

// Sabemos que la propiedad/predicado P dentro del rango es una de estas:
// Caso 1) 0 0 0 0 0 0 ... 1 1 1 1 1 1 (comienza false, pero una vez que se vuelve true, se mantiene true)
// Caso 2) 1 1 1 1 1 1 ... 0 0 0 0 0 0 (comienza true, pero una vez que se vuelve false, se mantiene false)

// Declaramos las "fronteras", una izquierda y una derecha, ambas comienzan FUERA del rango de búsqueda
int a = -1; // extremo izquierdo del rango de búsqueda -1
int b = n; // extremo derecho del rango de búsqueda +1
while(b - a > 1) { // mientras que la distancia entre las fronteras sea >1 (es decir, mientras que no estén contiguas)
    int m = (a + b) / 2; // punto medio
    if(P(m)) {
      // acá hacemos
      a = m; // dependiendo del caso 1 o 2, vamos a intercambiar si seteamos a o b, muy fácil de razonar!
    } else {
      b = m; // acá simplemente seteamos la otra frontera!
    }
}

// Al final del proceso, sabemos que las fronteras quedaron una al lado de otra, entonces dependiendo
// del problema van a ser:
// `a` la última para cual la función da true, y `b` la primera para la cual la función da false
// `a` la última para cual la función da false, y `b` la primera para la cual la función da true
// Si una de las fronteras me quedó fuera del rango, es porque la propiedad es siempre true (o siempre false)

// Luego es muy fácil razonar cuál de las dos fronteras queremos, siempre dependiendo del problema!

// Si la complejidad de evaluar P(x) es O(p), entonces la complejidad queda O(p log n).
// Muchas veces basta con que podamos calcular P en O(n), luego nos queda un algoritmo O(n log n)
// que es muy eficiente para muchos problemas!