Which is cheaper: sorting an array and then…

It depends on the context.

Single search in an unsorted array:
- Sort: Sorting complexity is usually $O(n \log n)$ or $O(n^2)$ (depends on the algorithm).
- Search (binary after sorting): $O(\log n)$.
- Total: $O(n \log n)$ or $O(n^2)$.
- Linear search (iteration): $O(n)$.
- Total: $O(n)$.
- In this case, linear search ($O(n)$) is cheaper than sorting + search ($O(n \log n)$ or worse).
Multiple searches in an array:
- If you need to perform $k$ searches in the same array.
- Sort once: $O(n \log n)$ or $O(n^2)$.
- Perform $k$ binary searches after sorting: $k \times O(\log n) = O(k \log n)$.
- Total: $O(n \log n + k \log n)$ or $O(n^2 + k \log n)$.
- Perform $k$ linear searches: $k \times O(n) = O(kn)$.
- Total: $O(kn)$.
- For large $k$ ($k > \log n$), sorting with subsequent binary search becomes cheaper: $O(n \log n + k \log n)$ vs $O(kn)$.
Special cases:
- If the array is already partially sorted or has a special structure, faster sorting or searching algorithms exist.
- Hash tables (Set or Hash in Ruby) provide average $O(1)$ search time, which is usually faster than any method based on sorting or linear search.

Conclusion: For a single search, linear search is cheaper. For multiple searches in the same array, sorting with subsequent binary search becomes more advantageous with a sufficiently large number of searches. If search speed is critical and data structure can be changed, using Set or Hash may be the most optimal solution.

Example of linear search in Ruby:

# Search for an element in an unsorted array
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Stop after finding the first match
  end
end

puts found # => 8

Example of sorting and binary search in Ruby (using built-in methods):

# Sorting
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n log n) for Timsort in Ruby

# Binary search (Ruby has built-in 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 "Element not found"
end

Which is cheaper: sorting an array and then searching, or using a linear search for an element?