Αλγόριθμοι - Binary Search

Ο αλγόριθμος Binary Search είναι ένας δημοφιλής, αποτελεσματικός και γρήγορος αλγόριθμος αναζήτησης.
Ο αλγόριθμος είναι σχετικά απλός αλλά προαπαιτεί ο πίνακας στον οποίον εφαρμόζεται να είναι ταξινομημένος.
Εφόσον έχουμε δώσει το στοιχείο που ψάχνουμε ξεκινάει ο αλγόριθμος :

1. Επιλέγουμε το μεσαίο στοιχείο του πίνακα και ελέγχουμε αν είναι το στοιχείο που ψάχνουμε.
2.1. Αν είναι το στοιχείο που ψάχνουμε η αναζήτηση τελειώνει.
2.2 Αν το στοιχείο που ψάχνουμε είναι μικρότερο από το μεσαίο στοιχείο του πίνακα τότε επαναπροσδιορίζουμε τον πίνακα ώστε η επόμενη αναζήτηση να γίνει στο μισό του πίνακα με τις μικρότερες τιμές.
2.3 Το αντίστοιχο γίνεται και αν το στοιχείο που ψάχνουμε είναι μεγαλύτερο από το μεσαίο στοιχείο του πίνακα.
3. Επαναλαμβάνουμε την ίδια διαδικασία ξεκινώντας από το βήμα 1. Μετά από λίγες μόνο επαναλήψεις και εφόσον το στοιχείο υπάρχει στο πίνακα, θα βρεθεί.

Θα υλοποιήσουμε ένα παράδειγμα με ένα πίνακα ακεραίων 1024 θέσεων.
Για να γίνει αυτό χρειάζονται μερικές βοηθητικές μεταβλητές :

import java.util.Random;

int mid;            //Το εκάστοτε μεσαίο στοιχείο του πίνακα
int left;           //Το αριστερό άκρο του πίνακα
int right;          //Το δεξί άκρο του πίνακα     
boolean found;      //Αν βρέθηκε το στοιχείο 

int[] sortedTable = new int[1024];

left = 0;
right = sortedTable.length() - 1; /**Το τελευταίο στοιχείο του πίνακα (η length() επιστρέφει το πλήθος 
των στοιχείων που υπάρχουνε στο πίνακα. 
Αν αυτά είναι 1024 τότε το τελευταίο στοιχείο του πίνακα είναι το 1023ο)
Έστω ότι ο πίνακας είναι ταξινομημένος με μοναδικές τιμές από το 0 έως το 1023 */
found = false;

Random generator = new Random();
int key = generator.nextInt(1024);   //Το στοιχείο που ψάχνουμε
found = false;

//Κι εδώ αρχίζει ουσιαστικά ο αλγόριθμος
while (left < right && found == false) {
   mid = (left + right) / 2;

   if (mid < key){ //Αν το στοιχείο μας είναι μεγαλύτερο από το μεσαίο στοιχειο του πίνακα
      left = mid + 1; /** Θέτουμε το αριστερό όριο το πίνακα ως το μεσαίο. Αυτό το κάνουμε
γιατί εφόσον το στοιχείο που ψάχνουμε βρίσκεται πάνω από τη μέση δεν υπάρχει λόγος να ψάξουμε τα 
στοιχεία αριστερά από το στοιχείο mid. */
      mid = left + right / 2;
   }
   else if (mid > key) { //Αν το στοιχείο μας είναι μικρότερο από το μεσαίο στοιχειο του πίνακα
      right = mid - 1; /** Θέτουμε το δεξιό όριο το πίνακα ως το μεσαίο. Αυτό το κάνουμε
γιατί εφόσον το στοιχείο που ψάχνουμε βρίσκεται κάτω από τη μέση δεν υπάρχει λόγος να ψάξουμε τα 
στοιχεία δεξιά από το στοιχείο mid.*/
      mid = left + right / 2;
   }
   else { //Αν το στοιχείο δεν είναι ούτε μεγαλύτερο όυτε μικρότερο... προφανώς βρέθηκε!
      System.out.println("Το στοιχείο βρέθηκε.");
      found = true;
   }
}

if (found == true) {
   System.out.println("Το στοιχείο βρίσκεται στη " + mid + " θέση του πίνακα.");
}
else {
   System.out.println("Το στοιχείο δε βρέθηκε.");
}

Worst case performance : log2(N) + 1;
η αλλιώς για ένα πίνακα 1024 ταξινομημένων στοιχείων η χειρότερη απόδοση του αλγορίθμου μπορεί να είναι log2(1024)+1 = 11, δηλαδή να βρεί τον αριθμό που θέλουμε μέσα σε 11 προσπάθειες.

Μεγέθη πινάκων και worst case performance :

-Δύναμη του 2-	-Πλήθος στοιχείων Πίνακα-	-WCP-
9	512	10
10	1024	11
11	2048	12
12	4096	13
13	8192	14
14	16384	15
15	32768	16
16	65536	17
32	4294967296	33
64	18446744073709551616	65