Ποια είναι η πολυπλοκότητα της αναζήτησης ενός στοιχείου σε έναν πίνακα σε Swift;

Η πολυπλοκότητα της αναζήτησης ενός στοιχείου σε έναν τυπικό μη ταξινομημένο πίνακα (π.χ., Array<Element>) στη Swift είναι O(n), όπου n είναι ο αριθμός των στοιχείων στον πίνακα. Αυτό οφείλεται στο γεγονός ότι, στην χειρότερη περίπτωση, μπορεί να χρειαστεί να διατρέξετε όλα τα στοιχεία του πίνακα για να βρείτε το στοιχείο.

Ωστόσο, αν ο πίνακας είναι ταξινομημένος, μπορείτε να χρησιμοποιήσετε την δυαδική αναζήτηση, η οποία έχει πολυπλοκότητα O(log n). Η Swift παρέχει τη μέθοδο binarySearch για ταξινομημένες συλλογές.

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

let array = [1, 5, 2, 8, 3]
let elementToFind = 8

for element in array {
    if element == elementToFind {
        // Βρέθηκε το στοιχείο
        break
    }
}

Παράδειγμα δυαδικής αναζήτησης σε ταξινομημένο πίνακα:

let sortedArray = [1, 2, 3, 5, 8]
let elementToFind = 5

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Το στοιχείο βρέθηκε στη θέση
}