Búsqueda lineal vs binaria: el poder de partir por la mitad
Buscar algo en una colección es el problema más cotidiano de la programación, y hay dos formas de hacerlo que no se parecen en nada. La búsqueda lineal mira uno a uno, de principio a fin: simple, funciona siempre, pero lenta. La búsqueda binaria parte la colección por la mitad una y otra vez y encuentra lo que buscas en un puñado de pasos, aunque haya millones de elementos. En esta segunda entrega de la serie de Algoritmos te explico las dos, su complejidad (O(n) frente a O(log n)), el requisito imprescindible de la binaria, sus versiones iterativa y recursiva, y cuándo usar cada una. Verás en acción esa diferencia brutal entre mirar un millón de cosas o solo veinte.