Δυαδική αναζήτηση
From Wikipedia, the free encyclopedia
Δυαδική αναζήτηση ονομάζεται ένας αναδρομικός αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε έναν ταξινομημένο μονοδιάστατο πίνακα. Ο αλγόριθμος αυτός χρησιμοποιεί την τεχνική Διαίρει και Βασίλευε. Εν γένει, η αναζήτηση σε έναν μη ταξινομημένο πίνακα γίνεται σε χρόνο γραμμικό ως προς το μέγεθος της εισόδου, συγκρίνοντας ένα προς ένα τα στοιχεία της εισόδου με το κλειδί. Όμως, η δυαδική αναζήτηση στηρίζεται στο γεγονός ότι ο πίνακας είναι ταξινομημένος, μειώνοντας έτσι σημαντικά τον αριθμό των συγκρίσεων που απαιτούνται.
Το λήμμα δεν περιέχει πηγές ή αυτές που περιέχει δεν επαρκούν. |
Εναλλακτικά μπορεί να χρησιμοποιηθεί κάποια άλλη δομή δεδομένων, αλλά είναι απαραίτητο αυτή να υποστηρίζει την τυχαία προσπέλαση σε σταθερό χρόνο, ώστε να διατηρηθεί η λογαριθμική ταχύτητα του αλγορίθμου. Για παράδειγμα, η δυαδική αναζήτηση δεν μπορεί να εφαρμοστεί σε μια δομή δεδομένων όπως η λίστα.