Búsqueda binaria

JavaScript · Unidad 22: Buscar y ordenar

Plan completo
JavaScript
10 ejercicios

Si la lista ya viene ordenada, buscar uno por uno es desperdiciar el orden. Mira el número de en medio: con eso ya sabes de qué lado está lo que buscas.

Y el otro lado lo descartas entero, sin mirarlo.

const ns = [2, 5, 8, 11, 14, 17];
const m = Math.floor((0 + 5) / 2);
console.log("miro", ns[m]);
console.log(11 > ns[m]);

Imprime

miro 8
true

El resto de la explicación está en la lección, que es del plan completo.

Ejercicios de esta lección

Se hacen en la app, que los corrige al momento y explica por qué.

1. Completa el código
Completa para mirar el número de en medio del tramo que va de izq a der.
2. Predice la salida
Se imprime cada número que mira la búsqueda. ¿Qué imprime?
3. Opción múltiple
¿Por qué la búsqueda binaria necesita que la lista esté ordenada?
4. Predice la salida
La lista no está ordenada y se busca el 9 de dos formas. ¿Qué imprime?
5. Encuentra el bug
La lista está ordenada y el 14 está en la posición 4, así que esto debería imprimir 4. ¿Qué línea tiene el error?
6. Ordena las líneas
Ordena la función que decide qué sigue después de mirar el número de en medio: si es el que buscas, listo; si es más chico, hay que seguir por la derecha; si no, por la izquierda.
7. Encuentra el caso que falla
donde(ns, v) recibe una lista ordenada y regresa la posición de v, o -1 si no está; con la lista vacía también regresa -1. ¿Con qué llamada falla?
8. Predice la salida
vueltas cuenta cuántas veces se mira un número al buscar el 8. ¿Qué imprime?
9. Completa el código
Completa para tener una copia ordenada, que es lo que la binaria necesita, sin desacomodar la lista original.
10. Opción múltiple
Tienes una lista desordenada de 100 nombres y necesitas buscar uno, una sola vez. ¿Qué conviene?

Hacer esta lección

Se abre en el navegador. Esta lección es del plan completo; la primera unidad de cada curso es gratis.

Ver todas las lecciones →