Για ποιο λόγο χρησιμοποιείται ο αλγόριθμος δυαδικής αναζήτησης;

Για αποτελεσματική αναζήτηση ενός στοιχείου σε έναν ταξινομημένο πίνακα.

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

Το πλεονέκτημα έναντι της γραμμικής αναζήτησης είναι η λογαριθμική χρονική πολυπλοκότητα, O(log n), ενώ στη γραμμική είναι O(n). Αυτό την καθιστά πολύ πιο γρήγορη για μεγάλους πίνακες.

Εφαρμογές:

• Αναζήτηση σε λεξικά και βάσεις δεδομένων (δείκτες).
• Αλγόριθμοι ταξινόμησης (π.χ., στο merge sort).
• Αναζήτηση του ριζικού στοιχείου μιας εξίσωσης.
• Αναζήτηση σε δομές δεδομένων τύπου δέντρων B.