Αναζήτηση

Ψάχνοντας μέσα σε δεδομένα

Κάθε φορά που γράφεις ένα όνομα στις επαφές του κινητού, που ένα eshop ελέγχει αν υπάρχει ένα προϊόν στην αποθήκη, που ο υπολογιστής της βιβλιοθήκης ψάχνει ένα βιβλίο, τρέχει ένας αλγόριθμος αναζήτησης: δίνεται μια λίστα και μια τιμή-στόχος, και ζητείται αν υπάρχει η τιμή στη λίστα και σε ποια θέση.

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

Σειριακή αναζήτηση

Η πιο απλή ιδέα: ξεκινάς από την αρχή και ελέγχεις τα στοιχεία ένα ένα, μέχρι να βρεις τον στόχο ή να τελειώσει η λίστα. Λέγεται σειριακή ή γραμμική αναζήτηση (linear search).

def seiriaki(lista, stoxos):
    for i in range(len(lista)):
        if lista[i] == stoxos:
            return i
    return -1

arithmoi = [42, 7, 19, 88, 3, 56]
print(seiriaki(arithmoi, 88))
print(seiriaki(arithmoi, 5))

3
-1

Η συνάρτηση επιστρέφει τη θέση του στόχου. Αν δεν τον βρει, επιστρέφει -1, μια τιμή που δεν μπορεί να είναι θέση και άρα σημαίνει «δεν υπάρχει». Πρόσεξε ότι το return -1 είναι έξω από τον βρόχο: εκτελείται μόνο αν ο βρόχος τελειώσει χωρίς να βρει τίποτα.

Χειρότερη περίπτωση είναι όταν ο στόχος είναι τελευταίος ή δεν υπάρχει καθόλου. Τότε η σειριακή αναζήτηση κάνει τόσες συγκρίσεις όσα είναι τα στοιχεία: για λίστα με $n$ στοιχεία, $n$ συγκρίσεις.

Το μεγάλο πλεονέκτημά της: δουλεύει σε οποιαδήποτε λίστα, ταξινομημένη ή όχι.

Δυαδική αναζήτηση

Σκέψου πώς ψάχνεις μια λέξη σε ένα έντυπο λεξικό. Δεν ξεκινάς από τη σελίδα $1$. Ανοίγεις κάπου στη μέση, βλέπεις ότι η λέξη σου είναι «πιο πριν», και πετάς όλο το δεύτερο μισό. Αυτό γίνεται μόνο επειδή το λεξικό είναι σε αλφαβητική σειρά.

Η δυαδική αναζήτηση (binary search) κάνει ακριβώς αυτό σε μια ταξινομημένη λίστα:

1. Κοιτάζει το μεσαίο στοιχείο του τμήματος που απομένει.
2. Αν είναι ο στόχος, τελείωσε.
3. Αν είναι μικρότερο από τον στόχο, ο στόχος μόνο στο δεξί μισό μπορεί να είναι. Αν είναι μεγαλύτερο, μόνο στο αριστερό.
4. Επαναλαμβάνει στο μισό που έμεινε, μέχρι να βρει τον στόχο ή να μη μείνει τίποτα.

def dyadiki(lista, stoxos):
    arxi = 0
    telos = len(lista) - 1
    while arxi <= telos:
        mesi = (arxi + telos) // 2
        if lista[mesi] == stoxos:
            return mesi
        elif lista[mesi] < stoxos:
            arxi = mesi + 1
        else:
            telos = mesi - 1
    return -1

taxin = [3, 8, 12, 17, 23, 31, 40, 52, 66]
print(dyadiki(taxin, 40))
print(dyadiki(taxin, 20))

6
-1

Οι μεταβλητές arxi και telos είναι οι δείκτες που οριοθετούν το κομμάτι της λίστας όπου μπορεί ακόμη να βρίσκεται ο στόχος. Η μέση υπολογίζεται με //, γιατί ο δείκτης πρέπει να είναι ακέραιος. Όταν το arxi ξεπεράσει το telos, το κομμάτι άδειασε και ο στόχος δεν υπάρχει.

Πίνακας βημάτων: δυαδική αναζήτηση του 20

Η λίστα είναι [3, 8, 12, 17, 23, 31, 40, 52, 66], με δείκτες 0 ως 8. Πριν πατήσεις, υπολόγισε τη νέα μέση.

Βήμα	Βήμα	arxi	telos	mesi	lista[mesi]	Απόφαση
Ζωντανή ενημέρωση

Επόμενο βήμαΌλαΕπαναφορά

Σειριακή εναντίον δυαδικής

Μεγάλωσε τη λίστα και μετακίνησε τον στόχο. Κοίτα πόσο αλλάζει η μία μπάρα και πόσο η άλλη.

Πλήθος στοιχείων100

Θέση του στόχου73

Η δυαδική θέλει ταξινομημένη λίστα. Η σειριακή όχι.

Συγκρίσεις για αυτή τη θέση

Σειριακή73

χειρότερη περίπτωση: 100

Δυαδική6

χειρότερη περίπτωση: 7

Άρα η επιλογή έχει κόστος: αν η λίστα αλλάζει συνέχεια και ψάχνεις σπάνια, ίσως δεν αξίζει να την ταξινομείς κάθε φορά. Αν ψάχνεις συχνά στα ίδια δεδομένα, η ταξινόμηση πληρώνεται μία φορά και κερδίζεται σε κάθε αναζήτηση. Γι' αυτό το επόμενο μάθημα είναι η ταξινόμηση.

Λυμένα παραδείγματα

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση

Δοκίμασέ το πρώτα. Μετά δες τη λύση.

Δείξε τη λύση