Trade-offs

¿Vale la pena ordenar?

Ordenar n valores cuesta del orden de n log n comparaciones (se ve en la ruta de Algoritmos). Una búsqueda lineal cuesta n. Ordenar solo compensa si vas a buscar muchas veces.

Tienes 10 000 valores sin ordenar y vas a hacer solo 3 búsquedas. ¿Qué conviene?Búsqueda lineal: ordenar cuesta más que mirar los 10 000 valores tres vecesBúsqueda binaria sobre el array tal como está, que descarta la mitad en cada pasoOrdenar y hacer búsqueda binaria: log n siempre es mejor que nOrdenar primero y después búsqueda lineal, para que termine antes en promedio