Implementación de la Búsqueda Binaria en JavaScript

Estás buscando en un array ordenado de 100,000 precios de productos. El método integrado indexOf() de JavaScript verifica cada elemento desde el inicio — eso son potencialmente 100,000 comparaciones. La búsqueda binaria lo hace en un máximo de 17. Esa diferencia es la razón por la que el algoritmo de búsqueda binaria en JavaScript importa, y por qué vale la pena escribirlo tú mismo — porque JavaScript no proporciona un método de búsqueda binaria integrado.

Este artículo cubre cómo funciona la búsqueda binaria, cómo implementar versiones tanto iterativas como recursivas, y cuándo usarla en lugar de la búsqueda lineal.

¿Qué es la Búsqueda Binaria y Por Qué Requiere un Array Ordenado?

La búsqueda binaria es un algoritmo de divide y vencerás. Funciona dividiendo repetidamente el espacio de búsqueda por la mitad hasta que encuentra el valor objetivo o agota todas las posibilidades.

Aquí está el detalle: solo funciona en arrays ordenados. El algoritmo asume que si el objetivo es mayor que el elemento del medio, debe estar en la mitad derecha. Esa suposición se rompe completamente con datos desordenados — obtendrías resultados incorrectos sin ningún error.

Los pasos son:

1. Encuentra el elemento del medio del rango de búsqueda actual
2. Si es igual al objetivo, devuelve su índice
3. Si el objetivo es menor, busca en la mitad izquierda
4. Si el objetivo es mayor, busca en la mitad derecha
5. Repite hasta encontrarlo o hasta que el rango de búsqueda esté vacío

Implementación de la Búsqueda Binaria en JavaScript: Enfoque Iterativo

La versión iterativa usa un bucle while y dos punteros. Es el enfoque preferido para la mayoría de los casos — legible, eficiente y usa espacio O(1).

function binarySearch(arr, target) {
  let start = 0
  let end = arr.length - 1

  while (start <= end) {
    const mid = Math.floor((start + end) / 2)

    if (arr[mid] === target) {
      return mid // Return the index
    } else if (arr[mid] < target) {
      start = mid + 1 // Search right half
    } else {
      end = mid - 1 // Search left half
    }
  }

  return -1 // Target not found
}

const prices = [10, 25, 47, 89, 134, 200]
console.log(binarySearch(prices, 89))  // 3
console.log(binarySearch(prices, 50))  // -1

Nota que esto devuelve el índice del objetivo, no un booleano. Eso es casi siempre más útil en la práctica.

Búsqueda Binaria Recursiva en JavaScript

La versión recursiva pasa índices de límite actualizados en cada llamada. Es elegante pero usa espacio de pila O(log n) — un frame por cada llamada recursiva.

function binarySearchRecursive(arr, target, start = 0, end = arr.length - 1) {
  if (start > end) return -1

  const mid = Math.floor((start + end) / 2)

  if (arr[mid] === target) return mid

  return arr[mid] < target
    ? binarySearchRecursive(arr, target, mid + 1, end)
    : binarySearchRecursive(arr, target, start, mid - 1)
}

const scores = [3, 11, 22, 45, 67, 91]
console.log(binarySearchRecursive(scores, 22))  // 2
console.log(binarySearchRecursive(scores, 50))  // -1

Un error común: olvidar hacer return de la llamada recursiva. Sin él, la función devuelve undefined incluso cuando el elemento existe.

Ordenar Antes de Buscar

Si tu array no está ya ordenado, necesitas ordenarlo primero. El método predeterminado Array.sort() de JavaScript ordena lexicográficamente, lo que rompe las comparaciones numéricas:

[10, 9, 100].sort()                   // [10, 100, 9] — incorrecto
[10, 9, 100].sort((a, b) => a - b)    // [9, 10, 100] — correcto

Siempre usa un comparador numérico para arrays de números antes de ejecutar la búsqueda binaria.

Búsqueda Binaria vs Búsqueda Lineal: Cuándo Usar Cada Una

Para un array de 10,000 elementos, la búsqueda lineal necesita hasta 10,000 comparaciones. La búsqueda binaria necesita como máximo 14. Si estás buscando una vez a través de un array pequeño y desordenado, indexOf() está bien. Si estás buscando repetidamente a través de datos grandes y ordenados, la búsqueda binaria es la herramienta correcta.

Conclusión

La búsqueda binaria es sencilla de implementar en JavaScript una vez que entiendes el requisito del array ordenado. Usa la versión iterativa por defecto — es más limpia y evita la sobrecarga de la pila de llamadas. Usa la versión recursiva cuando la estructura de tu código se beneficie de ella, pero recuerda siempre hacer return de la llamada recursiva. Y siempre verifica que tu array esté ordenado con un comparador numérico apropiado antes de buscar.

Preguntas Frecuentes

Complete picture for complete understanding

Capture every clue your frontend is leaving so you can instantly get to the root cause of any issue with OpenReplay — the open-source session replay tool for developers. Self-host it in minutes, and have complete control over your customer data.

Check our GitHub repo and join the thousands of developers in our community.