Τι είναι πιο φθηνό: να ταξινομήσετε έναν πίνακα και στη συνέχεια να κάνετε αναζήτηση, ή να χρησιμοποιήσετε μια γραμμική αναζήτηση για να βρείτε ένα στοιχείο;

Εξαρτάται από το πλαίσιο.

1. Μοναδική αναζήτηση σε μη ταξινομημένο πίνακα:

   • Ταξινόμηση: Η πολυπλοκότητα της ταξινόμησης είναι συνήθως $O(n \log n)$ ή $O(n^2)$ (ανάλογα με τον αλγόριθμο).
   • Αναζήτηση (δυαδική μετά την ταξινόμηση): $O(\log n)$.
   • Συνολικά: $O(n \log n)$ ή $O(n^2)$.
   • Γραμμική αναζήτηση (περίπλουν): $O(n)$.
   • Συνολικά: $O(n)$.
   • Σε αυτήν την περίπτωση, η περίπλεια ($O(n)$) είναι φθηνότερη από την ταξινόμηση + αναζήτηση ($O(n \log n)$ ή χειρότερα).

2. Πολλαπλές αναζητήσεις σε έναν πίνακα:

   • Αν χρειάζεται να πραγματοποιήσετε $k$ αναζητήσεις στον ίδιο πίνακα.
   • Μία φορά ταξινόμηση: $O(n \log n)$ ή $O(n^2)$.
   • Εκτελέστε $k$ δυαδικές αναζητήσεις μετά την ταξινόμηση: $k \times O(\log n) = O(k \log n)$.
   • Συνολικά: $O(n \log n + k \log n)$ ή $O(n^2 + k \log n)$.
   • Εκτελέστε $k$ γραμμικές περιηγήσεις: $k \times O(n) = O(kn)$.
   • Συνολικά: $O(kn)$.
   • Για μεγάλα $k$ ($k > \log n$), η ταξινόμηση με δυαδική αναζήτηση γίνεται πιο φθηνή: $O(n \log n + k \log n)$ έναντι $O(kn)$.

3. Ειδικές περιπτώσεις:

   • Αν ο πίνακας είναι ήδη μερικώς ταξινομημένος ή έχει ειδική δομή, υπάρχουν πιο γρήγοροι αλγόριθμοι ταξινόμησης ή αναζήτησης.
   • Οι πίνακες κατακερματισμού (Set ή Hash στη Ruby) προσφέρουν κατά μέσο όρο $O(1)$ χρόνο για αναζήτηση, που είναι συνήθως ταχύτερο από οποιαδήποτε μέθοδο βασισμένη στην ταξινόμηση ή γραμμική αναζήτηση.

Συμπέρασμα: Για μεμονωμένη αναζήτηση, η περιήγηση είναι φθηνότερη. Για πολλαπλές αναζητήσεις στον ίδιο πίνακα, η ταξινόμηση με δυαδική αναζήτηση γίνεται πιο αποδοτική όταν ο αριθμός των αναζητήσεων είναι αρκετά μεγάλος. Αν η ταχύτητα αναζήτησης είναι κρίσιμη και η δομή δεδομένων μπορεί να τροποποιηθεί, η χρήση Set ή Hash μπορεί να είναι η πιο βέλτιστη λύση.

Παράδειγμα γραμμικής αναζήτησης στη Ruby:

# Αναζήτηση στοιχείου σε μη ταξινομημένο πίνακα
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Διακοπή μετά την εύρεση πρώτης αντιστοιχίας
  end
end

puts found # => 8

Παράδειγμα ταξινόμησης και δυαδικής αναζήτησης στη Ruby (με χρήση των ενσωματωμένων μεθόδων):

# Ταξινόμηση
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) για Timsort στη Ruby

# Δυαδική αναζήτηση (Ruby διαθέτει 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 "Στοιχείο δεν βρέθηκε"
end