Πώς βρίσκεις μια τιμή σε ταξινομημένη λίστα κόβοντας στη μέση, και πόσα βήματα θέλει.
35 λεπτά
Θα μάθεις να
1Να εξηγείς γιατί η δυαδική αναζήτηση χρειάζεται ταξινομημένη λίστα και πώς μειώνει στο μισό τον χώρο αναζήτησης.
2Να γράφεις τη συνάρτηση binarySearch του βιβλίου σε Python, και στις δύο μορφές της (με found και με pos).
3Να εκτελείς τον αλγόριθμο με το χέρι, με τις τιμές των first, last και mid σε κάθε επανάληψη, και όταν το στοιχείο λείπει.
4Να βρίσκεις πόσα στοιχεία εξετάζονται το πολύ σε λίστα N στοιχείων, και να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά.
Βρες τον αριθμό
Σκέψου έναν αριθμό από το 1 ως το 1000. Η πρώτη ερώτηση είναι: «Είναι μικρότερος από το 500;». Όποια κι αν είναι η απάντηση, μένουν 500 υποψήφιοι αντί για 1000. Η δεύτερη ερώτηση, για το 250 ή για το 750, αφήνει 250. Κάθε ερώτηση κόβει τον χώρο αναζήτησης στο μισό.
Η σειριακή αναζήτηση, που ξέρεις από τη Β΄ τάξη, ελέγχει τα στοιχεία ένα ένα. Στη χειρότερη περίπτωση, όταν το στοιχείο είναι το τελευταίο ή δεν υπάρχει, τα ελέγχει όλα. Η δυαδική αναζήτηση εκμεταλλεύεται τη διάταξη των στοιχείων: χωρίζει κάθε φορά το σύνολο σε δύο ίσα μέρη και συνεχίζει μόνο στο μέρος όπου μπορεί να βρίσκεται το ζητούμενο.
Ο υπολογιστής μαντεύει
Στο βιβλίο ο υπολογιστής μαντεύει τον αριθμό που σκέφτεσαι. Χρειάζεται τρεις μεταβλητές: τα δύο άκρα του διαστήματος, 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 είναι πάντα ακέραιος. Το βιβλίο δείχνει το ίδιο παιχνίδι στο διάστημα 1 ως 16, με μυστικό αριθμό το 11:
Ο υπολογιστής βρίσκει το 11 από το 1 ως το 16
Υπολόγισε το mid με ακέραιη διαίρεση από τα first και last της ίδιας γραμμής, πριν πατήσεις.
Βήμα
first
last
mid
Απάντηση
Αλλάζει
Ζωντανή ενημέρωση
Οι μέσες ήταν 8, 12, 10 και 11: τέσσερις ερωτήσεις αντί για δεκαέξι. Με 1000 αριθμούς αρκούν 10, γιατί 210=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 θα αλλάξει.
Ξεκινάμε. Καμία μεταβλητή δεν έχει ακόμα τιμή.Γραμμή 15: τι τιμή θα πάρει το A;Γραμμή 15: το A παίρνει την τιμή [5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70].Γραμμή 16: καλείται η binarySearch([5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70], 45). Οι μεταβλητές της είναι δικές της.Γραμμή 2: τι τιμή θα πάρει το first;Γραμμή 2: το first παίρνει την τιμή 0.Γραμμή 3: τι τιμή θα πάρει το last;Γραμμή 3: το last παίρνει την τιμή 13.Γραμμή 4: τι τιμή θα πάρει το pos;Γραμμή 4: το pos παίρνει την τιμή -1.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 6.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → False.Γραμμή 9: η συνθήκη array[mid] < key είναι…Γραμμή 9: array[mid] < key → True.Γραμμή 10: τι τιμή θα πάρει το first;Γραμμή 10: το first παίρνει την τιμή 7.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 10.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → False.Γραμμή 9: η συνθήκη array[mid] < key είναι…Γραμμή 9: array[mid] < key → False.Γραμμή 12: τι τιμή θα πάρει το last;Γραμμή 12: το last παίρνει την τιμή 9.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 8.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → True.Γραμμή 8: τι τιμή θα πάρει το pos;Γραμμή 8: το pos παίρνει την τιμή 8.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → False.Γραμμή 13: τι θα επιστρέψει η binarySearch([5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70], 45);Γραμμή 13: η binarySearch([5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70], 45) επιστρέφει 8.Γραμμή 16: εμφανίζεται «8».Γραμμή 17: καλείται η binarySearch([5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70], 33). Οι μεταβλητές της είναι δικές της.Γραμμή 2: τι τιμή θα πάρει το first;Γραμμή 2: το first παίρνει την τιμή 0.Γραμμή 3: τι τιμή θα πάρει το last;Γραμμή 3: το last παίρνει την τιμή 13.Γραμμή 4: τι τιμή θα πάρει το pos;Γραμμή 4: το pos παίρνει την τιμή -1.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 6.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → False.Γραμμή 9: η συνθήκη array[mid] < key είναι…Γραμμή 9: array[mid] < key → False.Γραμμή 12: τι τιμή θα πάρει το last;Γραμμή 12: το last παίρνει την τιμή 5.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 2.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → False.Γραμμή 9: η συνθήκη array[mid] < key είναι…Γραμμή 9: array[mid] < key → True.Γραμμή 10: τι τιμή θα πάρει το first;Γραμμή 10: το first παίρνει την τιμή 3.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 4.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → False.Γραμμή 9: η συνθήκη array[mid] < key είναι…Γραμμή 9: array[mid] < key → True.Γραμμή 10: τι τιμή θα πάρει το first;Γραμμή 10: το first παίρνει την τιμή 5.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → True.Γραμμή 6: τι τιμή θα πάρει το mid;Γραμμή 6: το mid παίρνει την τιμή 5.Γραμμή 7: η συνθήκη array[mid] == key είναι…Γραμμή 7: array[mid] == key → False.Γραμμή 9: η συνθήκη array[mid] < key είναι…Γραμμή 9: array[mid] < key → True.Γραμμή 10: τι τιμή θα πάρει το first;Γραμμή 10: το first παίρνει την τιμή 6.Γραμμή 5: η συνθήκη first <= last and pos == -1 είναι…Γραμμή 5: first <= last and pos == -1 → False.Γραμμή 13: τι θα επιστρέψει η binarySearch([5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70], 33);Γραμμή 13: η binarySearch([5, 10, 17, 23, 28, 30, 35, 40, 45, 50, 60, 63, 68, 70], 33) επιστρέφει -1.Γραμμή 17: εμφανίζεται «-1».Τέλος: το πρόγραμμα ολοκληρώθηκε.
Όχι — ξανακοίτα τη γραμμή και τις τιμές που έχουν τώρα οι μεταβλητές.
Υπολόγισε το mid με ακέραιη διαίρεση από τα first και last της ίδιας γραμμής. Η τελευταία στήλη είναι η απόφαση της επανάληψης.
Βήμα
first
last
mid
array[mid]
Σύγκριση
Αλλάζει
Ζωντανή ενημέρωση
Όταν το στοιχείο δεν υπάρχει
Στην ίδια λίστα ψάχνεις το 33, που λείπει.
Αναζήτηση του 33
Πρόσεξε την τελευταία γραμμή: το first ξεπερνά το last και η συνθήκη της while γίνεται ψευδής.
Βήμα
first
last
mid
array[mid]
Σύγκριση
Αλλάζει
Ζωντανή ενημέρωση
Ο αλγόριθμος ισχύει για κάθε τύπο δεδομένων που συγκρίνεται με == και <: ακέραιους, πραγματικούς, και συμβολοσειρές σε αλφαβητική σειρά. Έτσι βρίσκεις ένα όνομα σε τηλεφωνικό κατάλογο.
Πόσα στοιχεία εξετάζονται
Κάθε επανάληψη κρατά το πολύ το μισό διάστημα. Για λίστα N στοιχείων, η χειρότερη περίπτωση βγαίνει χωρίς λογάριθμο: βρες τη μικρότερη δύναμη του 2 που ξεπερνά το N. Αν είναι 2k, εξετάζονται το πολύ k στοιχεία.
Στοιχεία N
7
14
16
100
1000
1.000.000
Σειριακή, το πολύ
7
14
16
100
1000
1.000.000
Δυαδική, το πολύ
3
4
5
7
10
20
Όταν η λίστα διπλασιάζεται, η σειριακή θέλει διπλάσιες συγκρίσεις και η δυαδική μία παραπάνω. Η καλύτερη περίπτωση της δυαδικής είναι μία σύγκριση: το ζητούμενο είναι ακριβώς στη μέση.
Σειριακή εναντίον δυαδικής
Ανέβασε το μέγεθος στα 1000 και άλλαξε τη θέση του ζητούμενου. Η δυαδική δεν ξεπερνά ποτέ τις 10 συγκρίσεις.
100
72
Η δυαδική θέλει ταξινομημένη λίστα. Η σειριακή δουλεύει σε κάθε λίστα.
Συγκρίσεις για αυτή τη θέση
Σειριακή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.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
1
Πρώτη επανάληψη:first = 0, last = 13, mid = (0 + 13) / 2 = 6, με ακέραιη διαίρεση. Είναι A[6] = 13 < 100, άρα first = 7.
Τέταρτη:mid = 13, A[13] = 99 < 100, first = 14. Τώρα first > last και ο βρόχος σταματά.
4
Συγκρίθηκαν οι 13, 89, 96, 99: τέσσερις συγκρίσεις. Η pos έμεινε -1, και αυτό επιστρέφεται.
Παράδειγμα 2
Να συμπληρώσετε τα κενά (1) ως (5), ώστε η συνάρτηση να εκτελεί δυαδική αναζήτηση του key στη λίστα array, σε αύξουσα σειρά.
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
1
def binarySearch(array, key):
first = 0
last = (1)
found = False
while first <= last and (2):
mid = (3)
if array[mid] == key:
found = True
elif array[mid] < key:
first = (4)
else:
last = (5)
return found
2
(1)len(array) - 1, η τελευταία θέση. (2)not found: ο βρόχος συνεχίζει όσο δεν έχει βρεθεί.
3
(3)(first + last) / 2, που ανάμεσα σε ακέραιους δίνει ακέραιο πηλίκο. (4)mid + 1 και (5)mid - 1: το mid έχει εξεταστεί και μένει έξω.
Παράδειγμα 3
Η λίστα codes έχει τους κωδικούς 7 προϊόντων σε αύξουσα σειρά και η prices τις τιμές τους, στις ίδιες θέσεις. Να γράψετε πρόγραμμα σε Python που διαβάζει κωδικούς μέχρι να δοθεί 0 και εμφανίζει για τον καθένα την τιμή του ή «Δεν υπάρχει».
Δοκίμασέ το πρώτα. Μετά δες τη λύση.
1
Η αναζήτηση γίνεται στη codes, που είναι ταξινομημένη. Η δεύτερη μορφή της binarySearch δίνει τη θέση, και η τιμή βρίσκεται στην ίδια θέση της prices.
2
Ο βρόχος είναι while με τιμή τερματισμού το 0: μία ανάγνωση πριν από αυτόν και μία στο τέλος του μπλοκ.
def binarySearch(array, key):
first = 0
last = len(array) - 1
pos = -1
while first <= last and pos == -1:
mid = (first + last) / 2
if array[mid] == key:
pos = mid
elif array[mid] < key:
first = mid + 1
else:
last = mid - 1
return pos
codes = [104, 117, 125, 138, 142, 156, 171]
prices = [2.5, 4.0, 1.2, 7.8, 3.0, 12.5, 6.0]
code = input("Κωδικός: ")
while code != 0:
pos = binarySearch(codes, code)
if pos != -1:
print "Τιμή:", prices[pos]
else:
print "Δεν υπάρχει"
code = input("Κωδικός: ")
3
Για τους κωδικούς 138, 120, 171 και 0 εμφανίζει Τιμή: 7.8, Δεν υπάρχει, Τιμή: 6.0. Κάθε κλήση ξεκινά πάλι με first = 0 και last = 6, γιατί είναι τοπικές μεταβλητές της συνάρτησης. Η input δίνει αριθμό, όπως στο βιβλίο. Ο έλεγχος γίνεται με pos != -1 και όχι με if pos:, γιατί ένα προϊόν στη θέση 0 θα έδινε 0, που η Python το διαβάζει ως ψευδές.
Πολλαπλή επιλογή
Πολλαπλή επιλογήΆσκηση 1 από 10
Ασκήσεις
ΒασικήΆσκηση 1 από 6
Στη λίστα A = [4, 9, 15, 22, 31, 40, 52] εκτελείται δυαδική αναζήτηση. Ποιο στοιχείο εξετάζεται πρώτο, και σε ποια θέση είναι;
Τα κατάφερες;
Να εξηγείς γιατί η δυαδική αναζήτηση χρειάζεται ταξινομημένη λίστα και πώς μειώνει στο μισό τον χώρο αναζήτησης.
Να γράφεις τη συνάρτηση binarySearch του βιβλίου σε Python, και στις δύο μορφές της (με found και με pos).
Να εκτελείς τον αλγόριθμο με το χέρι, με τις τιμές των first, last και mid σε κάθε επανάληψη, και όταν το στοιχείο λείπει.
Να βρίσκεις πόσα στοιχεία εξετάζονται το πολύ σε λίστα N στοιχείων, και να προσαρμόζεις τον αλγόριθμο σε φθίνουσα σειρά.
Λύσε τις ασκήσεις πιο πάνω και θα δεις εδώ πού στέκεσαι.