4.3 Μέθοδος διαίρει και βασίλευε

Στην κατηγορία "Διαίρει και Βασίλευε" (divide and conquer) εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα, που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα αλλά είναι μικρότερα σε μέγεθος. Με όμοιο τρόπο, τα υπο-προβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κοκ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να καταλήξουμε στη συνολική λύση του αρχικού ευρύτερου προβλήματος. Αυτή η προσέγγιση ονομάζεται από επάνω προς τα κάτω (top-down).

Πιο τυπικά, η περιγραφή αυτής της μεθόδου σχεδίασης αλγορίθμων μπορεί να αποδοθεί με τα επόμενα βήματα: 1. Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος. 2. Υποδιαιρείται το στιγμιότυπο του προβλήματος σε υπο-στιγμιότυπα του ίδιου προβλήματος. 3. Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο. 4. Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υπο-στιγμιότυπα, έτσι ώστε να δοθεί η συνολική λύση του προβλήματος.

Στη συνέχεια παρουσιάζεται ένας κλασικός αλγόριθμος που ακολουθεί τη φιλοσοφία της μεθόδου Διαίρει και Βασίλευε: η Δυαδική αναζήτηση.