Implementación Algoritmo de Búsqueda Binaria - Conceptos Básicos

• ¿Qué es la Búsqueda Binaria?
• Implementación en JavaScript
• Comparación con otros algoritmos similares

En este tutorial, exploraremos el algoritmo de Búsqueda Binaria, que es uno de los métodos más eficientes para encontrar un elemento en una lista ordenada. Aprenderemos cómo funciona y cómo implementarlo en JavaScript.

¿Qué es la Búsqueda Binaria?

La Búsqueda Binaria es un algoritmo utilizado para hallar la posición de un elemento en una lista ordenada. Es más eficiente que la búsqueda lineal debido a que reduce el área de búsqueda a la mitad en cada paso. Este algoritmo funciona dividiendo repetidamente el rango de búsqueda en dos mitades y comparando el elemento buscado con el elemento del medio.

Implementación en JavaScript

Aquí tienes un ejemplo de implementación del algoritmo de Búsqueda Binaria en JavaScript:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let steps = 0; // Solo para fines de demostración de complejidad

  while (left <= right) {
    steps++; // Solo para fines de demostración de complejidad
    const middle = Math.floor((left + right) / 2);
    if (arr[middle] === target) {
      console.log(`El algoritmo de búsqueda binaria realizó ${steps} pasos`); // Solo para fines de demostración de complejidad
      return middle;
    } else if (arr[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }

  return -1; // Elemento no encontrado
}

// Ejemplo de uso:
const array = [0, 4, 7, 10, 14, 23, 45, 47, 53];
const target = 47;
const result = binarySearch(array, target);
console.log("resultado", result); // índice del elemento Recuerda que los índices empiezan en 0)

Antes de la explicación, veamos una pequeña animación de como funciona el código anterior.

Explicación del código

• Definimos la función `binarySearch` que toma dos parámetros: `arr` (el arreglo ordenado) y `target` (el elemento que queremos encontrar).
• Inicializamos dos variables, `left` y `right`, que representan los límites izquierdo y derecho del rango de búsqueda.
• Utilizamos un bucle `while` que se ejecuta mientras `left` sea menor o igual a `right`.
• Calculamos el índice del elemento del medio usando `Math.floor((left + right) / 2)`.
• Comparamos el elemento del medio con el `target`.
• Si son iguales, retornamos el índice del medio.
• Si el elemento del medio es menor que el `target`, ajustamos `left` para que sea el índice del medio más uno.
• Si el elemento del medio es mayor que el `target`, ajustamos `right` para que sea el índice del medio menos uno.
• Si no encontramos el `target`, retornamos -1 para indicar que el elemento no está en el arreglo.

Comparación con otros algoritmos similares

Recuerda que la Búsqueda Binaria solo funciona en arreglos que ya están ordenados. Si el arreglo no está ordenado, deberás ordenarlo primero, lo que podría añadir complejidad adicional a tu solución.

¡Espero que este tutorial te haya sido útil! Ahora tienes una herramienta más para optimizar tus búsquedas en JavaScript.