Búsqueda lineal y binaria

Búsqueda

Búsqueda lineal — O(n)

Recorre el array elemento a elemento hasta encontrar el objetivo. Funciona con cualquier array, ordenado o no.

function busquedaLineal(arr, objetivo) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === objetivo) return i;
  }
  return -1;
}

Búsqueda binaria — O(log n)

Mucho más rápida, pero requiere un array ordenado. La idea: mirar el centro y descartar la mitad que no puede contener el objetivo, repitiendo.

function busquedaBinaria(arr, objetivo) {
  let inicio = 0;
  let fin = arr.length - 1;
  while (inicio <= fin) {
    const medio = Math.floor((inicio + fin) / 2);
    if (arr[medio] === objetivo) return medio;
    if (arr[medio] < objetivo) inicio = medio + 1;
    else fin = medio - 1;
  }
  return -1;
}

Con un millón de elementos, la búsqueda lineal puede hacer un millón de comparaciones; la binaria, solo unas 20.

Ejemplos

Búsqueda binaria paso a paso

function busquedaBinaria(arr, objetivo) {
  let inicio = 0, fin = arr.length - 1;
  while (inicio <= fin) {
    const medio = Math.floor((inicio + fin) / 2);
    console.log("Reviso índice", medio, "valor", arr[medio]);
    if (arr[medio] === objetivo) return medio;
    if (arr[medio] < objetivo) inicio = medio + 1;
    else fin = medio - 1;
  }
  return -1;
}
console.log("Encontrado en:", busquedaBinaria([1, 3, 5, 7, 9, 11], 9));