O que é mais barato: ordenar um array e depois…

Depende do contexto.

Procura única num array não ordenado:
- Ordenar: A complexidade de ordenar é geralmente $O(n \log n)$ ou $O(n^2)$ (depende do algoritmo).
- Procura (binária após ordenar): $O(\log n)$.
- Total: $O(n \log n)$ ou $O(n^2)$.
- Percurso (procura linear): $O(n)$.
- Total: $O(n)$.
- Neste caso, percorrer ($O(n)$) é mais barato do que ordenar + procurar ($O(n \log n)$ ou mais).
Procura múltipla num array:
- Se precisar realizar $k$ buscas no mesmo array.
- Ordenar uma vez: $O(n \log n)$ ou $O(n^2)$.
- Realizar $k$ buscas binárias após ordenar: $k \times O(\log n) = O(k \log n)$.
- Total: $O(n \log n + k \log n)$ ou $O(n^2 + k \log n)$.
- Realizar $k$ percursos lineares: $k \times O(n) = O(kn)$.
- Total: $O(kn)$.
- Para grandes $k$ ($k > \log n$), ordenar com busca binária torna-se mais barato: $O(n \log n + k \log n)$ vs $O(kn)$.
Casos especiais:
- Se o array já estiver parcialmente ordenado ou tiver uma estrutura especial, existem algoritmos de ordenação ou procura mais rápidos.
- As tabelas hash (Set ou Hash em Ruby) oferecem em média $O(1)$ tempo para procurar, o que geralmente é mais rápido do que qualquer método baseado em ordenação ou procura linear.

Conclusão: Para procura única, percorrer é mais barato. Para múltiplas buscas no mesmo array, ordenar com busca binária torna-se mais eficiente com um número suficiente de buscas. Se a velocidade de procura for crucial e a estrutura de dados puder ser alterada, usar Set ou Hash pode ser a solução mais ótima.

Exemplo de procura linear em Ruby:

# Procura de elemento em array não ordenado
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Parar após encontrar a primeira correspondência
  end
end

puts found # => 8

Exemplo de ordenação e procura binária em Ruby (usando métodos padrão):

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

# Procura binária (Ruby tem 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 não encontrado"
end

O que é mais barato: ordenar um array e depois procurar, ou usar uma busca por varredura para encontrar um elemento?