Informática · La búsqueda binaria
¿Cómo encontrar un nombre entre un millón en 20 pasos?
Lo que verás
Una guía telefónica tiene un millón de nombres, en orden alfabético. Revisarlos uno a uno podría costar un millón de vistazos. ¿Se puede hacer mejor? Ábrela justo por la mitad. El nombre que buscas va después, así que toda la primera mitad desaparece. Quedan medio millón. Abre por la mitad lo que queda, y vuelve a partirlo en dos. Y otra vez. Cada vistazo descarta la mitad de lo que queda. Veinte mitades llevan un millón hasta uno, porque dos elevado a veinte es poco más de un millón. ¿Mil millones de nombres? Solo diez vistazos más.
