Διαφορά μεταξύ δυαδικής αναζήτησης και γραμμικής αναζήτησης

Δυαδική αναζήτηση έναντι γραμμικής αναζήτησης

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

Τι είναι η Γραμμική Αναζήτηση;

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

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

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

Ποια είναι η διαφορά μεταξύ της Δυαδικής αναζήτησης και της Γραμμικής αναζήτησης;

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