Δυαδική αναζήτηση
Δυαδική αναζήτηση ονομάζεται ένας αναδρομικός αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο "στοιχείο-κλειδί") σε έναν ταξινομημένο μονοδιάστατο πίνακα. Ο αλγόριθμος αυτός χρησιμοποιεί την τεχνική Διαίρει και Βασίλευε. Εν γένει, η αναζήτηση σε έναν μη ταξινομημένο πίνακα γίνεται σε χρόνο γραμμικό ως προς το μέγεθος της εισόδου, συγκρίνοντας ένα προς ένα τα στοιχεία της εισόδου με το κλειδί. Όμως, η δυαδική αναζήτηση στηρίζεται στο γεγονός ότι ο πίνακας είναι ταξινομημένος, μειώνοντας έτσι σημαντικά τον αριθμό των συγκρίσεων που απαιτούνται.

Εναλλακτικά μπορεί να χρησιμοποιηθεί κάποια άλλη δομή δεδομένων, αλλά είναι απαραίτητο αυτή να υποστηρίζει την τυχαία προσπέλαση σε σταθερό χρόνο, ώστε να διατηρηθεί η λογαριθμική ταχύτητα του αλγορίθμου. Για παράδειγμα, η δυαδική αναζήτηση δεν μπορεί να εφαρμοστεί σε μια δομή δεδομένων όπως η λίστα.
Q179976
αναδρομικός
Concept
Q8366
αλγόριθμος
Concept
Q755673
αναζήτησης
Concept
Q671298
Διαίρει και Βασίλευε
Concept
Q175263
δομή δεδομένων
Concept
Q27948
λίστα
Concept
Q243754
Δυαδική αναζήτηση
Concept
instance of
instance of
subclass of