El problema

Tenemos un array de números ordenado de menor a mayor y un número target.

Debemos crear una función que encuentre la posición de target dentro del array.

Si el número no existe, debemos devolver -1.

Ejemplo 1

const numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

const target = 72;

La respuesta debería ser:

8

Porque 72 está en la posición 8.

Ejemplo 2

const numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

const target = 50;

Como 50 no existe:

-1

La regla

Nuestra función debe tener esta forma:

function binarySearch(numbers, target) {
    // nuestra solución
}

Y debería funcionar así:

console.log(
    binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 72)
);
// 8

console.log(
    binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 50)
);
// -1

---

Una solución que todos conocemos

Antes de complicarnos la vida, podríamos hacer esto:

function search(numbers, target) {
    return numbers.indexOf(target);
}

Y técnicamente el problema estaría resuelto.

Pero hay una razón por la que este ejercicio es famoso.

Queremos aprender a aprovechar que el array está ordenado para hacer la búsqueda mucho más eficiente.

---

La idea

Tenemos:

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

Buscamos:

72

En lugar de comenzar por 2, miramos el elemento del medio:

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
                  ↑
                 23

Sabemos que:

72 > 23

Como el array está ordenado, podemos descartar todo lo que está a la izquierda de 23.

No necesitamos volver a mirarlo.

Nos queda:

[38, 56, 72, 91]

Volvemos a mirar el medio:

[38, 56, 72, 91]
          ↑
         72

Encontramos nuestro número.

La clave está en esto:

Cada comparación nos permite eliminar aproximadamente la mitad de las posibilidades.

---

Solución completa

Esta es una implementación completa y ejecutable en JavaScript:

function binarySearch(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left <= right) {
        const middle = left + Math.floor((right - left) / 2);

        if (numbers[middle] === target) {
            return middle;
        }

        if (numbers[middle] < target) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }

    return -1;
}


// Ejemplos

const numbers = [
    2, 5, 8, 12, 16,
    23, 38, 56, 72, 91
];

console.log(binarySearch(numbers, 72));
// 8

console.log(binarySearch(numbers, 23));
// 5

console.log(binarySearch(numbers, 2));
// 0

console.log(binarySearch(numbers, 100));
// -1

---

¿Cómo funciona el código?

Comenzamos definiendo los límites:

let left = 0;
let right = numbers.length - 1;

Al principio estamos diciendo:

"La respuesta puede estar en cualquier posición del array."

Después calculamos el elemento del medio:

const middle = left + Math.floor((right - left) / 2);

Ahora tenemos tres posibilidades.

1. Encontramos el elemento

if (numbers[middle] === target) {
    return middle;
}

Terminamos.

---

2. El elemento buscado es mayor

if (numbers[middle] < target) {
    left = middle + 1;
}

Como sabemos que el array está ordenado, todo lo que está antes del elemento middle puede descartarse.

Movemos left hacia adelante.

---

3. El elemento buscado es menor

Si llegamos aquí:

right = middle - 1;

Significa que target es menor que el elemento del medio.

Por lo tanto, descartamos la mitad derecha.

---

¿Por qué es tan rápido?

Una búsqueda tradicional puede necesitar revisar todos los elementos:

O(n)

Binary Search, en cambio, reduce el problema a la mitad en cada iteración:

1,000,000
    ↓
500,000
    ↓
250,000
    ↓
125,000
    ↓
...
    ↓
1

Por eso su complejidad es:

O(log n)

Para un millón de elementos, estamos hablando de aproximadamente 20 comparaciones, en lugar de potencialmente un millón.

---

El patrón que debemos aprender

Más que memorizar binarySearch(), lo interesante es reconocer el patrón:

Si los datos están ordenados y puedo descartar una parte completa después de una comparación, probablemente puedo utilizar Binary Search.

Esta idea aparece en muchos problemas que aparentemente no tienen nada que ver con buscar un número.

Por ejemplo:

Buscar un elemento
        ↓
Buscar el primer elemento que cumple una condición
        ↓
Buscar un valor mínimo/máximo
        ↓
Buscar dentro de un rango de posibles respuestas

Es decir, Binary Search no es solamente un algoritmo.

Es una forma de reducir sistemáticamente el espacio de búsqueda.

---

Una pregunta importante

Hay algo que debemos preguntarnos antes de utilizarlo:

¿Qué pasa si mi array no está ordenado?

Por ejemplo:

const numbers = [38, 5, 91, 12, 2, 72];

Ya no podemos hacer:

if (numbers[middle] < target) {
    // descartar la izquierda
}

porque el orden que necesitamos no existe.

Tendríamos que ordenar primero:

numbers.sort((a, b) => a - b);

Pero eso introduce otro coste.

Por eso Binary Search no es automáticamente mejor que indexOf().

La estructura de nuestros datos es parte del problema.

---

Conclusión

Binary Search es un algoritmo relativamente pequeño, pero contiene una idea fundamental de la programación:

La mejor solución muchas veces no consiste en hacer el trabajo más rápido, sino en descubrir qué trabajo no necesitamos hacer.

En este caso, cada comparación nos permite eliminar aproximadamente la mitad de las posibilidades.

Y pasar de:

O(n)

a:

O(log n)

puede representar una diferencia enorme cuando nuestros datos crecen.

Ese es precisamente el tipo de razonamiento que vale la pena aprender cuando estudiamos algoritmos.