Πώς να BS (δυαδική αναζήτηση) το CS

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

Οι περισσότεροι άνθρωποι, όταν αντιμετωπίζουν μια άγνωστη πρόκληση, τείνουν να φρικάρουν, κάτι που είναι φυσιολογικό, αλλά ελπίζουμε ότι αφού διαβάσετε αυτό θα είστε πολύ πιο σίγουροι όταν αντιμετωπίζετε μια νέα πρόκληση.

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

Βήμα 1 - Αξιολογήστε τις τρέχουσες γνώσεις σας για το θέμα.

Όταν αντιμετωπίζετε κάποιο πρόβλημα, κάντε ένα βήμα πίσω και αναλύστε το πρόβλημα.

Το Πανεπιστήμιο της Ιντιάνα έκανε μια μελέτη σε μια ομάδα μαθητών και ανακάλυψε μερικούς ενδιαφέροντες τρόπους για να βελτιώσει τη διαδικασία εκμάθησης σας χρησιμοποιώντας ορισμένες τεχνικές μάθησης που βοηθούν στην ανάλυση της κατάστασης. Ξεκινήστε θέτοντας ερωτήσεις: τι γνωρίζετε για το θέμα; Βλέπετε κάποια σχέδια;

Η διερευνητική ανάκριση είναι μια μεγάλη τεχνική για να ξεκινήσετε τη διαδικασία σκέψης σας.

Βήμα 2 - Σχεδιάστε / γράψτε το πρόβλημα έξω.

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

Βήμα 3 - Συζήτηση.

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

Βήμα 4 - Σπάστε το.

Ακριβώς όπως το κάνουμε τώρα, πάρτε το βήμα προς βήμα.

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

Ας πάμε σε αυτό

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

Επανάληψη & Επανάληψη

Η επανάληψη είναι η πράξη της επανάληψης μιας διαδικασίας, είτε για να δημιουργηθεί μια απεριόριστη ακολουθία αποτελεσμάτων είτε για να προσεγγίσετε έναν επιθυμητό στόχο. Κάθε επανάληψη της διαδικασίας ονομάζεται «επανάληψη». Το αποτέλεσμα μιας επανάληψης χρησιμοποιείται ως σημείο εκκίνησης για την επόμενη επανάληψη.

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

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

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

Ταξινόμηση επιλογής

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

Ας ψευδο:

Φανταστείτε ότι μόλις τελειώσατε να πλένετε και ενώ διπλώνετε τα ρούχα σας, βρήκατε 8 διαφορετικά ζευγάρια κάλτσες με διαφορετικά μεγέθη από 1 έως 12, αλλά τα βρείτε χωρίς διαλογή [5, 7, 1, 8, 5, 2, 12] το πάτωμα του υπνοδωματίου, τώρα πρέπει να τα παραλάβετε, ώστε να μπορείτε να τα βάλετε στο ντουλάπι σας. Αρχίζετε με την πρώτη κάλτσα που βρίσκεται μπροστά σας. Η πρώτη κάλτσα που πήρατε ήταν η κάλτσα αριθ. 5 και υποθέσατε ότι η πρώτη κάλτσα που πήρατε είναι ταξινομημένη, κοιτάξτε στο πάτωμα για το μικρότερο μέγεθος κάλτσες που βλέπετε μπροστά σας, στην περίπτωση αυτή, τον αριθμό 1, τώρα συγκρίνετε αν αυτή που έχετε πάρει είναι μεγαλύτερο ή μικρότερο από αυτό που είχατε πριν, αν ο αριθμός είναι μικρότερος μπορείτε να ανταλλάξετε την μικρότερη τιμή μεγέθους με την πρώτη κάλτσα που σηκώσατε. Μόλις γίνει αυτό, θα πάρετε την επόμενη κάλτσα μπροστά σας 7, ελέγξτε και πάλι για το μικρότερο μέγεθος κάλτσες που βλέπετε μπροστά σας, το οποίο θα είναι 2, είναι 2 <7; Ναί! Αλλάξτε το μικρότερο μέγεθος για το τρέχον μέγεθος που συγκρίνεται [1, 2, 5, 8, 5, 12]. Κρατήστε το βρόχο μέσα από τις κάλτσες μέχρι ό, τι έχει ταξινομηθεί. Θυμηθείτε ότι μια ταξινομημένη λίστα είναι σε αύξουσα σειρά, πράγμα που σημαίνει ότι οι χαμηλότεροι αριθμοί παραμένουν στην αριστερή πλευρά και μεγαλύτεροι αριθμοί προς τη δεξιά πλευρά.

Ταξινόμηση φούσκα

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

Ας ψευδο:

Φανταστείτε ότι βρίσκεστε σε βιβλιοθήκη και ψάχνετε για ένα συγκεκριμένο βιβλίο του Χάρι Πότερ, αλλά είναι πολύ δύσκολο να βρείτε το βιβλίο που αναζητάτε επειδή το βιβλιοθήκη είναι πολύ βρώμικο και όχι σε τάξη [1, 4, 5, 2 , 6, 3, 7], οπότε αποφασίζετε να το οργανώσετε από τον όγκο κάθε βιβλίου με τα μικρότερα βιβλία προς τα αριστερά και τα μεγαλύτερα βιβλία προς τα δεξιά.

Έτσι πρώτα κοιτάζετε την αρχή του βιβλίου και συγκρίνετε το πρώτο και το δεύτερο βιβλίο μεταξύ τους, είναι 1> 4; Οχι! Αυτό σημαίνει ότι το πρώτο στοιχείο της λίστας είναι ήδη ταξινομημένο, οπότε τώρα συγκρίνετε το επόμενο ζευγάρι, είναι 4> 5; Οχι! Συγκρίνετε λοιπόν το επόμενο ζευγάρι, είναι 5> 2; Ναί! Τώρα μπορείτε να τις ανταλλάξετε [1, 4, 2, 5, 6, 3, 7] και συνεχίζετε να σκέφτεστε μέχρι να ταξινομηθούν όλα τα βιβλία [1, 2, 3, 4, 5, 6, 7].

Ταξινόμηση εισαγωγής

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

Ας ψευδο:

Είναι Παρασκευή το βράδυ και εσείς και οι φίλοι σας γιορτάζετε το Σαββατοκύριακο και έχοντας καλό χρόνο. Οι φίλοι σας αποφάσισαν να παίξουν το Uno, καθώς το παιχνίδι αρχίζει να παίρνετε μια ποσότητα 7 καρτών, καθώς αναλύετε τις κάρτες σας παρατηρείτε ότι δεν είναι σε τάξη [5, 7, 2, 4, 3, 8, 9] για να αναδιατάξετε τις κάρτες σας ξεκινάτε από την αρχή, η κάρτα σας πρώτα θα ρυθμιστεί σαν να είναι ταξινομημένη, τώρα κοιτάξτε την επόμενη αδιατάρακτη κάρτα και τώρα εισαγάγετε την στο ταξινομημένο τμήμα μετατοπίζοντας τον απαιτούμενο αριθμό καρτών.

Γραμμική αναζήτηση

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

Ας ψευδο:

Φανταστείτε ότι είστε έτοιμοι να βγείτε, αλλά ψάχνετε για το αγαπημένο σας πουκάμισο, ώστε να μπορείτε να ταιριάξετε με το υπόλοιπο της στολή σας, κοιτάζετε το πουκάμισο με το πουκάμισό σας, αν βρείτε το πουκάμισο που ψάχνετε για να σταματήσετε, αλλιώς , συνεχίστε μέσα από το ντουλάπι σας.

Δυαδική αναζήτηση

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

Ας ψευδο:

Ψάχνετε για τον ορισμό μιας λέξης σε ένα λεξικό, ένα λεξικό είναι πάντα ταξινομημένο με αλφαβητική σειρά, ας πούμε ότι ψάχνετε τη λέξη Rainbow, ώστε να πάτε στη μέση του λεξικού και να πάρετε το γράμμα G, αν R (που είναι το πρώτο γράμμα της λέξης που ψάχνουμε) είναι <(χαμηλότερη) από το G που πηγαίνουμε αριστερά και αν είναι> (μεγαλύτερη) κινούμαστε δεξιά. Σε αυτή την περίπτωση είναι μεγαλύτερη, ώστε να απορρίψουμε την αριστερή πλευρά και να πάμε προς τα μέσα του δεξιού τμήματος και να επαναλάβουμε τη λειτουργία μέχρι να βρείτε τη λέξη RAINBOW.

Περίληψη

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

Μεγάλοι πόροι παρακολούθησης:
 Ones και Zeros, οι μαγικοί ήρωες που κάνουν τον κόσμο να πάει 'γύρο
 Github Αναδρομικές Εξισώσεις Πολυπλοκότητας
 Συνέντευξη Github Coding Πανεπιστήμιο
 Cracking της συνέντευξης κωδικοποίησης, 6η έκδοση
 Επανεξέταση Κάντε διαφάνειες των αλγορίθμων της Σχολής
 Διαβάστε το άρθρο της Συνέντευξης του κέικ σχετικά με την ιδέα πίσω από τη μεγάλη σημείωση Ο
 Διαβάστε το άρθρο του Συνέντευξη Cake σχετικά με τους λογαρίθμους και τη δυαδική αναζήτηση
Παρακολουθήστε τα βίντεο αναδρομικών αλγορίθμων του HackerRank, το βίντεο με αλγόριθμους αναζήτησης δυαδικών ψηφίων και το βίντεο μεγάλου μήκους Ο
Παρακολουθήστε το παλιό βίντεο αναδρομής του Χάρβαρντ, το νέο βίντεο αναδρομής, το video frame stack, το γραμμικό βίντεο αναζήτησης, το δυαδικό βίντεο αναζήτησης, το ασυμπτωτικό βίντεο συμβολισμού και το βίντεο υπολογιστικής πολυπλοκότητας
Τίτλος δημιουργήθηκε από τον TJ King
 Κολοκύθα κώδικα
 Tutorials Point