¿Qué es más barato: ordenar un array y luego buscar…

Depende del contexto.

Búsqueda única en un array no ordenado:
- Ordenar: La complejidad de ordenar suele ser $O(n \log n)$ o $O(n^2)$ (depende del algoritmo).
- Búsqueda (binaria después de ordenar): $O(\log n)$.
- Total: $O(n \log n)$ o $O(n^2)$.
- Búsqueda lineal (recorrido): $O(n)$.
- Total: $O(n)$.
- En este caso, recorrer ($O(n)$) es más barato que ordenar + buscar ($O(n \log n)$ o más).
Búsqueda múltiple en un array:
- Si necesitas realizar $k$ búsquedas en el mismo array.
- Ordenar una vez: $O(n \log n)$ o $O(n^2)$.
- Realizar $k$ búsquedas binarias después de ordenar: $k \times O(\log n) = O(k \log n)$.
- Total: $O(n \log n + k \log n)$ o $O(n^2 + k \log n)$.
- Realizar $k$ recorridos lineales: $k \times O(n) = O(kn)$.
- Total: $O(kn)$.
- Para grandes $k$ ($k > \log n$), ordenar con búsqueda binaria resulta más barato: $O(n \log n + k \log n)$ frente a $O(kn)$.
Casos especiales:
- Si el array ya está parcialmente ordenado o tiene una estructura especial, existen algoritmos de ordenamiento o búsqueda más rápidos.
- Las tablas hash (Set o Hash en Ruby) ofrecen en promedio $O(1)$ tiempo para buscar, lo cual suele ser más rápido que cualquier método basado en ordenamiento o búsqueda lineal.

Conclusión: La búsqueda única es más barata con recorrido. Para búsquedas múltiples en el mismo array, ordenar y usar búsqueda binaria es más eficiente con un número suficiente de búsquedas. Si la velocidad de búsqueda es crucial y la estructura de datos puede modificarse, usar Set o Hash puede ser la opción más óptima.

Ejemplo de búsqueda lineal en Ruby:

# Buscar un elemento en un array no ordenado
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Detenerse tras encontrar la primera coincidencia
  end
end

puts found # => 8

Ejemplo de ordenamiento y búsqueda binaria en Ruby (usando métodos estándar):

# Ordenar
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n log n) para Timsort en Ruby

# Búsqueda binaria (Ruby tiene bsearch)
target = 8
index = sorted_array.bsearch_index { |x| x >= target } # O(log n)

if index && sorted_array[index] == target
  puts sorted_array[index] # => 8
else
  puts "Elemento no encontrado"
end

¿Qué es más barato: ordenar un array y luego buscar, o usar una búsqueda por recorrido para encontrar un elemento?