Buna ziua doamnelor si domnilor si bine v-am regasit. Ma numesc Zero Davila, iar astazi vom implementa in java o forma al algoritmului de cautare Divide and Conquer, si anume cautarea binara, utilizand un arbore binar. Un arbore binar e constituit din mai multe noduri care contin o valoare si 0, 1 sau 2 succesori. Nodul din stanga va avea o valoare mai mica iar cel din dreapta mereu va avea o valoare mai mare. Fiecare nod are un singur predecesor, cu exceptia radacinii care nu are niciunul. Deci daca avem un array de 9 elemente iar noi vrem sa cautam pozitia cheii 4, intai fragmentam array-ul in 2 bucati. Pentru ca 4 e mai mic decat 5 cautam in nodurile din stanga al arborelui,
pentru ca 5 e radacina, mijlocul array-ului, si asa am injumatatit deja elementele in care trebuie sa cautam. In stanga
avem elementul 2, 4 e mai mare decat 2 asa ca vom continua sa cautam in dreapta, si am injumatatit elementele din nou. Am ajuns la elementul 3, 4 e mai mare decat 3, si il vom gasii la urmatorul nod succesor din dreapta.
public class BinarySearch {
public int binarySearch(int[] inputArr, int key) {
int start = 0;
int end = inputArr.length – 1;
while (start <= end) {
int mid = (start + end) / 2;
if (key == inputArr[mid]) {
return mid;
} if (key < inputArr[mid]) {
end = mid – 1;
} else {
start = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
BinarySearch binary = new BinarySearch();
int[] arr = { 2,4,6,8,10,12,14,16 };
System.out.println(„Pozitia elementului 14 : ” + binary.binarySearch(arr, 14));
int[] arr1 = { 6,34,78,12,432,9000 };
System.out.println(„Pozitia elementului 432 : ” + binary.binarySearch(arr1, 432));
}
}
Algoritm de cautare Divide and Conquer.
_____________________________________
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Arbore binar.
_____
| 5 |
/ \
/ \
_____ _____
| 2 | | 7 |
/ | | \
/ | | \
_____ _____ _____ _____
| 1 | | 3 | | 6 | | 8 |
\ \
\ \
_____ _____
| 4 | | 9 |