Μετάβαση στο περιεχόμενο

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

Πώς βρίσκεις μια τιμή σε ταξινομημένη λίστα κόβοντας στη μέση, και πόσα βήματα θέλει.

35 λεπτά

Θα μάθεις να

  1. Να εξηγείς γιατί η δυαδική αναζήτηση χρειάζεται ταξινομημένη λίστα και πώς μειώνει στο μισό τον χώρο αναζήτησης.
  2. Να γράφεις τη συνάρτηση binarySearch του βιβλίου σε Python, και στις δύο μορφές της (με found και με pos).
  3. Να εκτελείς τον αλγόριθμο με το χέρι, με τις τιμές των first, last και mid σε κάθε επανάληψη, και όταν το στοιχείο λείπει.
  4. Να βρίσκεις πόσα στοιχεία εξετάζονται το πολύ σε λίστα N στοιχείων, και να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά.

Βρες τον αριθμό

Σκέψου έναν αριθμό από το 11 ως το 10001000. Η πρώτη ερώτηση είναι: «Είναι μικρότερος από το 500500;». Όποια κι αν είναι η απάντηση, μένουν 500500 υποψήφιοι αντί για 10001000. Η δεύτερη ερώτηση, για το 250250 ή για το 750750, αφήνει 250250. Κάθε ερώτηση κόβει τον χώρο αναζήτησης στο μισό.

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

Ο υπολογιστής μαντεύει

Στο βιβλίο ο υπολογιστής μαντεύει τον αριθμό που σκέφτεσαι. Χρειάζεται τρεις μεταβλητές: τα δύο άκρα του διαστήματος, first και last, και το μέσο του, mid. Κάθε απάντηση μετακινεί ένα από τα δύο άκρα.

# Ο άνθρωπος σκέφτεται έναν αριθμό από 1 έως 1000
N = 1000
print "Σκέψου έναν αριθμό από το 1 έως το", N
guesses = 0
found = False
first = 1
last = N
while not found and guesses < 10:
    mid = (first + last) / 2
    answer = raw_input("Είναι ο αριθμός ο " + str(mid) + " ? (N/O)")
    guesses = guesses + 1
    if answer == "N":
        found = True
    else:
        answer = raw_input("Είναι μικρότερος του " + str(mid) + " ?")
        if answer == "N":
            last = mid - 1
        else:
            first = mid + 1
if found:
    print "Κέρδισα!!! Το βρήκα με", guesses, "προσπάθειες"
else:
    print "Κέρδισες"

Στην Python 2.7 το / ανάμεσα σε ακέραιους είναι ακέραιη διαίρεση: το (1 + 1000) / 2 κάνει 500, όχι 500.5. Έτσι το mid είναι πάντα ακέραιος. Το βιβλίο δείχνει το ίδιο παιχνίδι στο διάστημα 11 ως 1616, με μυστικό αριθμό το 1111:

Ο υπολογιστής βρίσκει το 11 από το 1 ως το 16

Υπολόγισε το mid με ακέραιη διαίρεση από τα first και last της ίδιας γραμμής, πριν πατήσεις.

ΒήμαfirstlastmidΑπάντησηΑλλάζει
Ζωντανή ενημέρωση

Οι μέσες ήταν 88, 1212, 1010 και 1111: τέσσερις ερωτήσεις αντί για δεκαέξι. Με 10001000 αριθμούς αρκούν 1010, γιατί 210=10242^{10} = 1024.

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

Η ίδια ιδέα δουλεύει σε μια λίστα array, αρκεί τα στοιχεία της να είναι ταξινομημένα. Τα άκρα τώρα είναι θέσεις της λίστας: ξεκινούν από 0 και len(array) - 1. Αυτή είναι η συνάρτηση του βιβλίου, για λίστα σε αύξουσα σειρά:

def binarySearch(array, key):
    first = 0
    last = len(array) - 1
    found = False
    while first <= last and not found:
        mid = (first + last) / 2
        if array[mid] == key:
            found = True
        elif array[mid] < key:
            first = mid + 1
        else:
            last = mid - 1
    return found

Επιστρέφει True αν το key υπάρχει στη λίστα και False αν όχι. Τις περισσότερες φορές όμως θέλεις και τη θέση του. Στη δεύτερη μορφή η λογική μεταβλητή found αντικαθίσταται από τη pos, που ξεκινά από -1. Όσο μένει -1, το στοιχείο δεν έχει βρεθεί. Μόλις βρεθεί, κρατά τη θέση του.

Στον runner που ακολουθεί το μέσο γράφεται (first + last) // 2, που δίνει το ίδιο αποτέλεσμα με το (first + last) / 2 του βιβλίου στην 2.7. Το print(...) με ένα όρισμα δουλεύει ίδια και στις δύο εκδόσεις.

Η θέση του 45 σε 14 αριθμούς

Η λίστα του βιβλίου. Πριν από κάθε σύγκριση πες ποιο στοιχείο είναι το array[mid] και ποιο από τα first, last θα αλλάξει.

  1. def binarySearch(array, key):
  2. first = 0
  3. last = len(array) - 1
  4. pos = -1
  5. while first <= last and pos == -1:
  6. mid = (first + last) // 2
  7. if array[mid] == key:
  8. pos = mid
  9. elif array[mid] < key:
  10. first = mid + 1
  11. else:
  12. last = mid - 1
  13. return pos
  14. τρέχουσα γραμμή: A = [5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70]
  15. print(binarySearch(A, 45))
  16. print(binarySearch(A, 33))

Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.Γραμμή 15: τι τιμή θα πάρει το A;

Μεταβλητές

—

Έξοδος

Τα first, last και mid για το 45

Υπολόγισε το mid με ακέραιη διαίρεση από τα first και last της ίδιας γραμμής. Η τελευταία στήλη είναι η απόφαση της επανάληψης.

Βήμαfirstlastmidarray[mid]ΣύγκρισηΑλλάζει
Ζωντανή ενημέρωση

Όταν το στοιχείο δεν υπάρχει

Στην ίδια λίστα ψάχνεις το 3333, που λείπει.

Αναζήτηση του 33

Πρόσεξε την τελευταία γραμμή: το first ξεπερνά το last και η συνθήκη της while γίνεται ψευδής.

Βήμαfirstlastmidarray[mid]ΣύγκρισηΑλλάζει
Ζωντανή ενημέρωση

Ο αλγόριθμος ισχύει για κάθε τύπο δεδομένων που συγκρίνεται με == και <: ακέραιους, πραγματικούς, και συμβολοσειρές σε αλφαβητική σειρά. Έτσι βρίσκεις ένα όνομα σε τηλεφωνικό κατάλογο.

Πόσα στοιχεία εξετάζονται

Κάθε επανάληψη κρατά το πολύ το μισό διάστημα. Για λίστα NN στοιχείων, η χειρότερη περίπτωση βγαίνει χωρίς λογάριθμο: βρες τη μικρότερη δύναμη του 22 που ξεπερνά το NN. Αν είναι 2k2^k, εξετάζονται το πολύ kk στοιχεία.

Στοιχεία NN7714141616100100100010001.000.0001.000.000
Σειριακή, το πολύ7714141616100100100010001.000.0001.000.000
Δυαδική, το πολύ3344557710102020

Όταν η λίστα διπλασιάζεται, η σειριακή θέλει διπλάσιες συγκρίσεις και η δυαδική μία παραπάνω. Η καλύτερη περίπτωση της δυαδικής είναι μία σύγκριση: το ζητούμενο είναι ακριβώς στη μέση.

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

Ανέβασε το μέγεθος στα 1000 και άλλαξε τη θέση του ζητούμενου. Η δυαδική δεν ξεπερνά ποτέ τις 10 συγκρίσεις.

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

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

Σειριακή73

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

Δυαδική6

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

Φθίνουσα σειρά

Αν η λίστα είναι ταξινομημένη από το μεγαλύτερο στο μικρότερο, οι μικρότερες τιμές είναι δεξιά. Όταν array[mid] > key, το ζητούμενο είναι δεξιά. Αλλάζει μόνο ο τελεστής της elif:

if array[mid] == key:
    pos = mid
elif array[mid] > key:
    first = mid + 1
else:
    last = mid - 1

Οι αναθέσεις στα first και last μένουν ίδιες.

Παραδείγματα

Παράδειγμα 1

Δίνεται η λίστα A = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 94, 96, 99]. Να γράψετε τους αριθμούς που θα συγκριθούν με το 100 κατά την εκτέλεση της δυαδικής αναζήτησης, και τι θα επιστρέψει η συνάρτηση με τη pos.

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

Παράδειγμα 2

Να συμπληρώσετε τα κενά (1) ως (5), ώστε η συνάρτηση να εκτελεί δυαδική αναζήτηση του key στη λίστα array, σε αύξουσα σειρά.

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

Παράδειγμα 3

Η λίστα codes έχει τους κωδικούς 7 προϊόντων σε αύξουσα σειρά και η prices τις τιμές τους, στις ίδιες θέσεις. Να γράψετε πρόγραμμα σε Python που διαβάζει κωδικούς μέχρι να δοθεί 0 και εμφανίζει για τον καθένα την τιμή του ή «Δεν υπάρχει».

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

Πολλαπλή επιλογή

Πολλαπλή επιλογήΆσκηση 1 από 10
Σωστό ή Λάθος: «Η δυαδική αναζήτηση μπορεί να εφαρμοστεί σε οποιαδήποτε λίστα αριθμών.»

Ασκήσεις

ΒασικήΆσκηση 1 από 6

Στη λίστα A = [4, 9, 15, 22, 31, 40, 52] εκτελείται δυαδική αναζήτηση. Ποιο στοιχείο εξετάζεται πρώτο, και σε ποια θέση είναι;

Τα κατάφερες;

  • Να εξηγείς γιατί η δυαδική αναζήτηση χρειάζεται ταξινομημένη λίστα και πώς μειώνει στο μισό τον χώρο αναζήτησης.
  • Να γράφεις τη συνάρτηση binarySearch του βιβλίου σε Python, και στις δύο μορφές της (με found και με pos).
  • Να εκτελείς τον αλγόριθμο με το χέρι, με τις τιμές των first, last και mid σε κάθε επανάληψη, και όταν το στοιχείο λείπει.
  • Να βρίσκεις πόσα στοιχεία εξετάζονται το πολύ σε λίστα N στοιχείων, και να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά.

Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.

Βρήκες κάποιο λάθος;