Δυαδική αναζήτηση έναντι Γραμμικής αναζήτησης
Η γραμμική αναζήτηση, γνωστή και ως διαδοχική αναζήτηση, είναι ο απλούστερος αλγόριθμος αναζήτησης. Αναζητά μια καθορισμένη τιμή σε μια λίστα ελέγχοντας κάθε στοιχείο της λίστας. Η δυαδική αναζήτηση είναι επίσης μια μέθοδος που χρησιμοποιείται για τον εντοπισμό μιας καθορισμένης τιμής σε μια ταξινομημένη λίστα. Η μέθοδος δυαδικής αναζήτησης μειώνει κατά το ήμισυ τον αριθμό των στοιχείων που ελέγχονται (σε κάθε επανάληψη), μειώνοντας τον χρόνο που απαιτείται για τον εντοπισμό του δεδομένου στοιχείου στη λίστα.
Τι είναι η Γραμμική αναζήτηση;
Η γραμμική αναζήτηση είναι η απλούστερη μέθοδος αναζήτησης, η οποία ελέγχει κάθε στοιχείο σε μια λίστα διαδοχικά μέχρι να βρει ένα καθορισμένο στοιχείο. Η είσοδος στη μέθοδο γραμμικής αναζήτησης είναι μια ακολουθία (όπως ένας πίνακας, μια συλλογή ή μια συμβολοσειρά) και το στοιχείο που πρέπει να αναζητηθεί. Η έξοδος είναι true εάν το καθορισμένο στοιχείο βρίσκεται εντός της παρεχόμενης ακολουθίας ή false εάν δεν είναι στην ακολουθία. Εφόσον αυτή η μέθοδος ελέγχει κάθε στοιχείο της λίστας μέχρι να βρεθεί το καθορισμένο στοιχείο, στη χειρότερη περίπτωση θα περάσει από όλα τα στοιχεία της λίστας πριν βρει το απαιτούμενο στοιχείο. Η πολυπλοκότητα της γραμμικής αναζήτησης είναι o(n). Επομένως, θεωρείται ότι είναι πολύ αργό για να χρησιμοποιηθεί κατά την αναζήτηση στοιχείων σε μεγάλες λίστες. Αλλά αυτό είναι πολύ απλό και πιο εύκολο στην εφαρμογή.
Τι είναι η δυαδική αναζήτηση;
Η δυαδική αναζήτηση είναι επίσης μια μέθοδος που χρησιμοποιείται για τον εντοπισμό ενός καθορισμένου στοιχείου σε μια ταξινομημένη λίστα. Αυτή η μέθοδος ξεκινά συγκρίνοντας το στοιχείο που αναζητήθηκε με τα στοιχεία στη μέση της λίστας. Εάν η σύγκριση καθορίσει ότι τα δύο στοιχεία είναι ίσα, η μέθοδος σταματά και επιστρέφει τη θέση του στοιχείου. Εάν το στοιχείο που αναζητήθηκε είναι μεγαλύτερο από το μεσαίο στοιχείο, ξεκινά ξανά τη μέθοδο χρησιμοποιώντας μόνο το κάτω μισό της ταξινομημένης λίστας. Εάν το στοιχείο αναζήτησης είναι μικρότερο από το μεσαίο στοιχείο, ξεκινά τη μέθοδο ξανά χρησιμοποιώντας μόνο το επάνω μισό της ταξινομημένης λίστας. Εάν το στοιχείο που αναζητήθηκε δεν βρίσκεται στη λίστα, η μέθοδος θα επιστρέψει μια μοναδική τιμή που το υποδεικνύει. Επομένως, η μέθοδος δυαδικής αναζήτησης μειώνει στο μισό τον αριθμό των στοιχείων που συγκρίνονται (σε κάθε επανάληψη), ανάλογα με το αποτέλεσμα της σύγκρισης. Συνεπώς, η δυαδική αναζήτηση εκτελείται σε λογαριθμικό χρόνο με αποτέλεσμα o(log n) μέση απόδοση περίπτωσης.
Ποια είναι η διαφορά μεταξύ δυαδικής αναζήτησης και γραμμικής αναζήτησης;
Αν και η γραμμική αναζήτηση και η δυαδική αναζήτηση είναι μέθοδοι αναζήτησης, έχουν αρκετές διαφορές. Ενώ η δυαδική αναζήτηση λειτουργεί σε ταξινομημένες λίστες, η γραμμική αναζήτηση μπορεί να λειτουργήσει και σε μη ταξινομημένες λίστες. Η ταξινόμηση μιας λίστας έχει γενικά μια μέση πολυπλοκότητα υπόθεσης n log n. Η γραμμική αναζήτηση είναι απλή και απλή στην υλοποίηση από τη δυαδική αναζήτηση. Ωστόσο, η γραμμική αναζήτηση είναι πολύ αργή για να χρησιμοποιηθεί με μεγάλες λίστες λόγω της μέσης απόδοσής της σε περίπτωση o(n). Από την άλλη πλευρά, η δυαδική αναζήτηση θεωρείται ότι είναι μια πιο αποτελεσματική μέθοδος που θα μπορούσε να χρησιμοποιηθεί με μεγάλες λίστες. Ωστόσο, η εφαρμογή της δυαδικής αναζήτησης θα μπορούσε να είναι αρκετά δύσκολη και μια μελέτη έδειξε ότι ο ακριβής κώδικας για τη δυαδική αναζήτηση θα μπορούσε να βρεθεί μόνο σε πέντε από τα είκοσι βιβλία.
