Binary search
Presentation
•
Computers
•
12th Grade
•
Hard
ΖΗΣΗΣ ΚΑΡΑΣΙΜΟΣ
Used 21+ times
FREE Resource
13 Slides • 6 Questions
1
Δυαδική αναζήτηση-Περιγραφή
Ο αλγόριθμος εφαρμόζεται μόνο σε πίνακες που έχουν ταξινομημένα στοιχεία. Ο αλγόριθμος λειτουργεί ως εξής:
1. Βρίσκουμε το μεσαίο στοιχείο του ταξινομημένου πίνακα.
2. Εάν το προς αναζήτηση στοιχείο είναι ίσο με το μεσαίο στοιχείο, τότε σταματάμε την αναζήτηση αφού το στοιχείο βρέθηκε.
3. Εάν δε βρέθηκε, τότε ελέγχουμε αν το στοιχείο που αναζητούμε είναι μικρότερο ή μεγαλύτερο από το μεσαίο στοιχείο του πίνακα. Αν είναι μικρότερο, περιορίζουμε την αναζήτηση στο πρώτο μισό του πίνακα (με την προϋπόθεση ότι τα στοιχεία είναι διατεταγμένα κατά αύξουσα σειρά), ενώ αν είναι μεγαλύτερο περιορίζουμε την αναζήτηση στο δεύτερο μισό του πίνακα.
4. Η διαδικασία αυτή επαναλαμβάνεται για το κατάλληλο πρώτο ή δεύτερο μισό του πίνακα, μετά για το 1/4 του πίνακα κοκ. μέχρι, είτε να βρεθεί το στοιχείο, είτε να μην είναι δυνατό να χωρισθεί ο πίνακας περαιτέρω σε δύο νέα μέρη.
2
Δυαδική αναζήτηση-Οπτικοποίηση
Στο διπλανό animation βλέπετε χαρακτηριστικά ην υπεροχή της δυαδικής αναζήτησης έναντι της σειριακής. Παρατηρήστε προσεκτικά την υστέρηση χρόνου της σειριακής!
3
Δυαδική αναζήτηση-Υπουργείο Παιδείας
Η δυαδική αναζήτηση διδάσκεται ως άσκηση και υλοποιείται με πρόγραμμα. Πέρα από το τμήμα δηλώσεων, το πρόγραμμα έχει επιπλέον τμήμα για το "γέμισμα" του πίνακα με στοιχεία. Υποθέτουμε ότι ο πίνακας γεμίζει με στοιχεία σε αύξουσα σειρά.
4
Δυαδική αναζήτηση
Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε αύξουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Εφαρμόστε στο τετράδιό σας τη δυαδική αναζήτηση για το στοιχείο 71.
5
Multiple Choice
Θα βρει το 71 μετά από:
2 συγκρίσεις
3 συγκρίσεις
8 συγκρίσεις
6
Δυαδική αναζήτηση
Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε φθίνουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Εφαρμόστε στο τετράδιό σας τη δυαδική αναζήτηση για το στοιχείο 71.
7
Multiple Choice
Θα βρει το 71 μετά από:
2 συγκρίσεις
3 συγκρίσεις
8 συγκρίσεις
8
Μέτρηση συγκρίσεων
Ένας μαθητής προσπαθεί να μετρήσει πόσες συγκρίσεις κάνει ο αλγόριθμος της δυαδικής αναζήτησης για να βρει ή όχι το 71, και σκέφθηκε να ορίσει έναν μετρητή c και να τον μηδενίσει στην αρχή.
9
10
Multiple Choice
Σε ποια θέση του κώδικα θα πρέπει να τοποθετήσει την εντολή καταμέτρησης των συγκρίσεων c <- c + 1 για να μετράει σωστά;
11
Δυαδική αναζήτηση
Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε αύξουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Αναζητείται το 71.
12
Τι λάθος γίνεται εδώ;
Ο κώδικας της επανάληψης της δυαδικής αναζήτησης εμφανίζεται ως εξής:
13
Multiple Choice
Αν τρέξει αυτός ο αλγόριθμος θα βγάλει:
Βρέθηκε το στοιχείο 71
Δεν βρέθηκε το στοιχείο 71
Δεν θα εμφανισθεί τίποτε
14
Δυαδική αναζήτηση
Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε αύξουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Αναζητείται το 71.
15
Τι λάθος γίνεται εδώ;
Ο κώδικας της επανάληψης της δυαδικής αναζήτησης εμφανίζεται ως εξής:
16
Multiple Choice
Αν τρέξει αυτός ο αλγόριθμος θα βγάλει:
Βρέθηκε το στοιχείο 71
Δεν βρέθηκε το στοιχείο 71
Δεν σταματάει η επανάληψη
17
Δυαδική αναζήτηση
Έστω ένας πίνακας με 9 στοιχεία, ταξινομημένος σε αύξουσα σειρά όπως φαίνεται στη διπλανή εικόνα. Αναζητείται το 71.
18
Τι λάθος γίνεται εδώ;
Ο κώδικας της επανάληψης της δυαδικής αναζήτησης εμφανίζεται ως εξής:
19
Multiple Choice
Αν τρέξει αυτός ο αλγόριθμος θα βγάλει:
Βρέθηκε το στοιχείο 71
Δεν βρέθηκε το στοιχείο 71
Δεν σταματάει η επανάληψη
Δυαδική αναζήτηση-Περιγραφή
Ο αλγόριθμος εφαρμόζεται μόνο σε πίνακες που έχουν ταξινομημένα στοιχεία. Ο αλγόριθμος λειτουργεί ως εξής:
1. Βρίσκουμε το μεσαίο στοιχείο του ταξινομημένου πίνακα.
2. Εάν το προς αναζήτηση στοιχείο είναι ίσο με το μεσαίο στοιχείο, τότε σταματάμε την αναζήτηση αφού το στοιχείο βρέθηκε.
3. Εάν δε βρέθηκε, τότε ελέγχουμε αν το στοιχείο που αναζητούμε είναι μικρότερο ή μεγαλύτερο από το μεσαίο στοιχείο του πίνακα. Αν είναι μικρότερο, περιορίζουμε την αναζήτηση στο πρώτο μισό του πίνακα (με την προϋπόθεση ότι τα στοιχεία είναι διατεταγμένα κατά αύξουσα σειρά), ενώ αν είναι μεγαλύτερο περιορίζουμε την αναζήτηση στο δεύτερο μισό του πίνακα.
4. Η διαδικασία αυτή επαναλαμβάνεται για το κατάλληλο πρώτο ή δεύτερο μισό του πίνακα, μετά για το 1/4 του πίνακα κοκ. μέχρι, είτε να βρεθεί το στοιχείο, είτε να μην είναι δυνατό να χωρισθεί ο πίνακας περαιτέρω σε δύο νέα μέρη.
Show answer
Auto Play
Slide 1 / 19
SLIDE
Similar Resources on Wayground
8 questions
Τα μόρια της ζωής
Presentation
•
12th Grade
8 questions
Προϊόντα ή Οικονομικά Αγαθά
Presentation
•
12th Grade
20 questions
ΜΟΝΤΕΛΟ OSI
Presentation
•
12th Grade
10 questions
Μηχανές Εσωτερικής Καύσης (ΜΕΚ) - Μάθημα 2
Presentation
•
12th Grade
10 questions
Ο ΧΡΩΜΑΤΙΚΟΣ ΚΥΚΛΟΣ
Presentation
•
KG - University
18 questions
Forms (HTML)
Presentation
•
10th - 12th Grade
7 questions
ΕΠΕΞΕΡΓΑΣΙΑ ΚΕΙΜΕΝΟΥ-ΠΛΗΚΤΡΟΛΟΓΙΟ
Presentation
•
12th Grade
9 questions
Η ΤΕΧΝΗ ΣΤΟ ΝΗΠΙΑΓΩΓΕΙΟ
Presentation
•
KG - University
Popular Resources on Wayground
24 questions
PBIS-HGMS Day 10
Quiz
•
6th - 8th Grade
10 questions
HCS SCI 03 Summer School Review 3
Quiz
•
3rd Grade
11 questions
Home Scope
Quiz
•
7th - 8th Grade
15 questions
HCS SCI 05 Summer School Assessment 3 Review
Quiz
•
5th Grade
35 questions
Lufkin Road Middle School Student Handbook & Policies Assessment
Quiz
•
7th Grade
18 questions
Geo 11.3 Area of Circles and Sectors
Quiz
•
9th - 11th Grade