Búsqueda binaria
Paso 1 de 7
objetivo16intentos0
mid
2
5
8
12
16
23
31
42
lo
hi
El array está ordenado, así que el elemento del medio te dice en qué mitad no puede estar el objetivo.
La idea
Con datos ordenados, compara el objetivo con el elemento del medio y descarta la mitad que no puede contenerlo. Repite hasta que quede un solo candidato. Esa división a la mitad te da O(log n).
Ejemplo del mundo real
Buscar a “Nadia” en los contactos de tu celular. Nunca bajas desde la A: saltas cerca del medio, caes por la M y de inmediato ignoras todo lo anterior. Dos o tres saltos después, ya llegaste.
El código
Te toca
Completa el espacio en blanco.
nums = [1, 3, 5, 7, 9]
lo, hi = 0, 4
mid = (lo + hi) // 2
# nums[mid] is 5 and the target is 9 -> search right
lo = ___Mini quiz
1 / 3