Ingeniero de Software: pregunta de entrevista
¿Cuándo es apropiada la búsqueda binaria?
La búsqueda binaria sirve para un predicado monótono sobre un espacio ordenado: cuando cambia, no vuelve atrás. Mantén invariantes explícitos de límites y trata bordes para evitar errores de uno.
Respuesta directa
Qué debe cubrir una buena respuesta
Cómo funciona
La búsqueda binaria aplica siempre que el espacio de respuestas pueda ordenarse de modo que una pregunta de sí o no sea falsa hasta cierto punto y verdadera después. La búsqueda clásica en un array ordenado es un caso; buscar la menor capacidad que cumple una restricción, la primera versión donde falla una prueba o el mayor valor que cabe en un presupuesto tienen la misma forma. La implementación mantiene dos límites con un invariante declarado sobre qué lado queda descartado, mueve un límite por iteración y comprueba explícitamente la condición de parada y los rangos vacíos para evitar errores de uno.
Ejemplo
Encontrar el primer commit que rompió la build es una búsqueda binaria sobre el historial porque una vez rota la build sigue rota; git bisect hace exactamente eso. Asignar la capacidad mínima de un barco para entregar paquetes en D días es una búsqueda binaria sobre valores de capacidad, porque si la capacidad C funciona, cualquier capacidad mayor también.
Errores frecuentes
- Aplicarla a datos sin ordenar o a un predicado que no es monótono.
- Escribir mid = (low + high) / 2 en un lenguaje donde la suma desborda.
- Equivocar la condición del bucle y devolver el límite incorrecto o iterar para siempre.
Una estructura útil para responder
Responde desde tu propia experiencia.
No memorices un guion: usa solo ejemplos que puedas explicar con honestidad en preguntas posteriores.
Abre el espacio de trabajo de escritorio y ensaya una respuesta clara con tus propias palabras.