Algoritmos JavaScript: búsqueda binaria

La búsqueda binaria asume que la matriz (o cualquier otra estructura de datos) en la que está buscando está ordenada.

Comenzamos con la matriz y el elemento que necesitamos buscar.

Miramos el medio de la matriz. Tomamos el número de elementos y lo dividimos entre 2. Imagina que tenemos una parte de la matriz a la izquierda y la otra parte a la derecha.

Si el artículo que tenemos es más bajo que el que buscamos, entonces debe estar en la parte correcta, para que podamos descartar por completo la parte de la derecha.

Luego realizamos la misma acción, dividiendo la parte derecha de la matriz en 2, mirando el elemento del medio y tiramos parte de la matriz.

Al final, obtendrá el artículo (o devolveránullsi no se encuentra el artículo).

Al final, si la matriz tiene 8 elementos, encontramos el elemento en 4 pasos como máximo.

Si la matriz tiene 32 elementos, tenemos un máximo de 6 pasos en el peor de los casos. En comparación con 32 en la búsqueda lineal, ¡es una gran optimización!

La búsqueda binaria tieneO(log n) complejidad.

Aquí hay una posible implementación de la misma:

const binarySearch = (list, item) => {
  let low = 0
  let high = list.length - 1

while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid]

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">===</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">mid</span>
}

<span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">guess</span> <span style="color:#f92672">&gt;</span> <span style="color:#a6e22e">item</span>) {
  <span style="color:#a6e22e">high</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>
} <span style="color:#66d9ef">else</span> {
  <span style="color:#a6e22e">low</span> <span style="color:#f92672">=</span> <span style="color:#a6e22e">mid</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>
}

}

return null //if not found }

¿Como funciona esto? Obtenemos ellistmatriz y el valor del elemento que estamos buscando. Luego inicializamos ellowvalor en 0 inicialmente, y elhighvalor al último índice de la lista. Primero miramos el artículo del medio, y si es lo que estamos buscando, lo devolvemos y terminamos. Si no, configuramos ellowohighvalores para mirar solo la parte izquierda o derecha de la matriz, y repetimos el proceso hasta encontrar el elemento.

Devolvemos el índice del elemento en la matriz:

console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0
console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4

Regresamosnullsi el elemento no se encuentra:

console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

Más tutoriales de js: