Τι είναι μια δυαδική αναζήτηση;

Υποθέστε ότι ένα άτομο έχει μια πολύ μεγάλη ποικιλία αντικειμένων και τα οργανώνει με κάποιο κανονικό τρόπο σε μια μακρά σειρά.Αυτό το άτομο μπορεί γρήγορα να καταλάβει πού στη σειρά ένα συγκεκριμένο αντικείμενο βρίσκεται χρησιμοποιώντας μια δυαδική αναζήτηση.Αυτή η αναζήτηση γίνεται με τον έλεγχο του μεσαίου αντικειμένου στη σειρά και αν το μεσαίο αντικείμενο δεν είναι το αντικείμενο που επιδιώκεται, στη συνέχεια κοιτάζοντας μόνο σε ένα από τα μισά της σειράς όπου θα μπορούσε να είναι το στοιχείο.Το άτομο θα γνωρίζει ποιο μισό θα συνεχίσει να κοιτάζει επειδή τα αντικείμενα είναι διατεταγμένα.Αυτά τα δύο βήματα γίνονται ξανά και ξανά, σε μικρότερα και μικρότερα μισά, μέχρι να βρεθεί το αντικείμενο ή δεν υπάρχει πουθενά.Βρίσκει τη θέση ή το δείκτη ενός στοιχείου σε ένα διαδοχικά ταξινομημένο σύνολο δεδομένων.Το επιτυγχάνει αυτό, συγκρίνοντας μια γνωστή τιμή με ένα καθορισμένο μεσαίο στοιχείο της συστοιχίας και, εάν δεν είναι ισοδύναμο, περιορίζοντας επανειλημμένα τη σύγκριση του μεσαίου στοιχείου με το μικρότερο σχετικό μισό του σετ μέχρι να ληφθεί μια ισοδυναμία ή ο κατάλογος εξαντληθεί.

Μια δυαδική αναζήτηση, μερικές φορές ονομάζεται αναζήτηση μισής διασύνδεσης, είναι πολύ ταχύτερη από μια βασική διαδοχική αναζήτηση που ξεκινά από το ένα άκρο μιας λίστας αντικειμένων και συγκρίνει κάθε στοιχείο στην πορεία μέχρι να βρεθεί ένας αγώνας ή μέχρι να φτάσει η αναζήτησητέλος της λίστας.Εάν ένα άτομο είχε 100 στη σειρά και το τελευταίο στοιχείο ήταν αυτό που αναζητούσε, μια διαδοχική αναζήτηση θα έπαιρνε 100 συγκρίσεις.Η μέθοδος διχοτόμησης, ωστόσο, απαιτεί μόνο επτά συγκρίσεις το πολύ πριν βρεθεί το στοιχείο.Είναι προφανώς πολύ πιο αποτελεσματικό από μια διαδοχική αναζήτηση.

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

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