Binary Search

Qué es una búsqueda binaria o Binary Search

Binary Search o búsqueda binaria, es una búsqueda también llamada de intervalo medio o logarítmica (de acuerdo a su Big O Notation). Parte de una colección de datos ordenada y busca el punto medio, descartando la parte donde no está el elemento y partiendo de nuevo a la mitad el sub conjunto donde si está. Supongamos que tenemos el siguiente arreglo de 15 elementos: [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30]
  • Primero tenemos que asegurarnos que los datos están ordenados, es un requisito. En este caso si lo están, de menor a mayor.
  • Necesitamos saber la posición del número 24 dentro del arreglo.

El algoritmo sería el siguiente:

  1. Se inicializan 3 variables: indiceInferior con 0, indiceSuperior con el tamaño del arreglo y elementoMedio la mitad entre ambos índices.
  2. Si el elemento que está en medio es igual al que buscamos, terminamos el algorirmo.
  3. Si es mayor, actualizamos el indiceInferior que toma el valor del elementoMedio
  4. Si es menor, actualizamos el indiceSuperior que toma el valor del elementoMedio
  5. Volemos a comarar hasta que encontremos el valor deseado o la diferencia entre indiceSuperior-indiceInferior sea menor o igual a 1.
El valor sería encontrado en 3 iteraciones de nuestro algoritmo. Esto nos da una notación de tiempo de O log(n), mucho mas eficiente que la búsqueda lineal que sería O(n). Este tipo de algoritmos también son llamados in place, ya que no requieren estructuras de datos adicionales (otro arreglo) para encontrar el resultado. [caption id="attachment_7309" align="aligncenter" width="800"]Binary Search Binary Search[/caption] [pastacode lang="javascript" manual="var%20binarySearch%20%3D%20(lookUp)%20%3D%3E%20%7B%0A%20%20let%20numbers%20%3D%20%5B1%2C%203%2C%204%2C%207%2C%209%2C%2011%2C%2013%2C%2016%2C%2019%2C%2018%2C%2020%2C%2022%2C%2024%2C%2027%2C%2030%5D%3B%0A%20%20let%20limitLeft%20%3D%200%3B%0A%20%20let%20limitRight%20%3D%20numbers.length%3B%0A%20%20let%20index%20%3D%20Math.round(numbers.length%20%2F%202)%3B%0A%20%20let%20count%20%3D%200%3B%0A%20%20%2F%2FPudiera%20darse%20el%20caso%20que%20encontremos%20el%20valor%20deseado%20incluso%20antes%0A%20%20%2F%2Fde%20iniciar%20a%20iterar%20en%20nuestro%20arreglo%0A%20%20if(numbers%5Bindex%5D%20%3D%3D%3D%20lookUp)%20%7B%0A%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20found%20at%20position%20'%20%2B%20index%20%2B%20'%20in%200%20iterations.'%3B%0A%20%20%7D%20else%20%7B%0A%20%20%20%20while(numbers%5Bindex%5D%20!%3D%3D%20lookUp%20%26%26%20(limitRight%20-%20limitLeft)%20%3E%201)%20%7B%0A%20%20%20%20%20%20%2F%2FContador%20de%20interaciones%0A%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%2F%2FEl%20n%C3%BAmero%20es%20mas%20grande%20que%20nuestro%20elemento%20medio%2C%0A%20%20%20%20%20%20%2F%2Factualizaremos%20nuestro%20l%C3%ADmite%20inferior%20al%20punto%20medio%20actual%0A%20%20%20%20%20%20if(lookUp%20%3E%20numbers%5Bindex%5D)%20%7B%0A%20%20%20%20%20%20%20%20limitLeft%20%3D%20index%3B%0A%20%20%20%20%20%20%20%20index%20%2B%3D%20Math.round((limitRight-limitLeft)%20%2F%202)%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%2F%2FEl%20n%C3%BAmero%20es%20mas%20peque%C3%B1o%20que%20nuestro%20elemento%20medio%2C%0A%20%20%20%20%20%20%2F%2Factualizaremos%20nuestro%20l%C3%ADmite%20superior%20al%20punto%20medio%20actual%0A%20%20%20%20%20%20else%20if(lookUp%20%3C%20numbers%5Bindex%5D)%20%7B%0A%20%20%20%20%20%20%20%20limitRight%20%3D%20index%3B%0A%20%20%20%20%20%20%20%20index%20-%3D%20Math.round((limitRight-limitLeft)%20%2F%202)%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%2F%2FLlevamos%20a%20cabo%20la%20comparaci%C3%B3n%2C%20si%20el%20elemento%20es%20encontrado%2C%0A%20%20%20%20%20%20%2F%2Fterminamos%20nuestro%20ciclo%0A%20%20%20%20%20%20if%20(numbers%5Bindex%5D%20%3D%3D%3D%20lookUp)%20%7B%0A%20%20%20%20%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20found%20at%20position%20'%20%2B%20index%20%2B%20'%20in%20'%20%2B%20count%20%2B%20'%20iterations.'%3B%0A%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%2F%2FNo%20se%20encontr%C3%B3%20el%20elemento%0A%20%20%20%20return%20'Number%20'%20%2B%20lookUp%20%2B%20'%20not%20found'%3B%0A%20%20%7D%0A%7D%3B%0A%0A%20console.log(binarySearch(24))%3B" message="Búsqueda Binaria" highlight="9,17,23,29,34" provider="manual"/] Aquí una liga con una buena referencia y amplia explicación de la búsqueda binaria.
Note to VCs: Aviada is not for sale. Please look somewhere else.