¿Qué debe cumplirse para poder usar búsqueda binaria en una lista?
Opciones
- La lista debe tener longitud par
- La lista debe estar ordenada (Opción correcta)
- La lista debe contener solo enteros
- La lista debe tener menos de 1000 elementos
Respuesta
La lista debe estar ordenada
Por qué
La búsqueda binaria decide qué mitad descartar comparando el objetivo con el elemento central. Eso solo tiene sentido si los valores menores están a la izquierda y los mayores a la derecha, es decir, si la lista está ordenada.
En una lista sin ordenar da respuestas incorrectas. Si buscas muchas veces, ordenar una vez (O(n log n)) y luego buscar (O(log n) cada vez) puede compensar.
Recuerda
La búsqueda binaria necesita datos ordenados.