binarySearch - Cautarea rapida a unui element in sir.

[Lux0R^]

| Afiseaza codul

/**
 * Finding a number in array in a very high speed. (Complexity O(log2(n))
 *
 * @note    Array needs to be sorted !
 *
 * @param Array		    Array for searching in.
 * @param Size		    Array size.
 * @param Finder		Number to find in array.
 * @return				Position of the number. If the number isn't found will return -1;
 */
 
public binarySearch(Array[], Size, Finder)
{
	new st = 0, dr = Size - 1, m;
	while ( st <= dr )
	{
		m = (st + dr) / 2;
		if ( Array[m] == Finder )
		{
			return m;
		}
			
		if ( x > Array[m] )
			st = m + 1;
		else
			dr = m - 1;
	}
	return -1;
}

Cautarea binara este una dintre cele mai eficiente cautari, ea va injumatatii sir-ul de fiecare data cand nu gaseste elementul cautat.

exemplu :
avem sirul de dimenstiune 10 :
0 1 2 3 4 5 6 7 8 9
iar noi vom cauta elementul 7:
cautarea va incepe de la mijloc, adica de la elementul 5, cu valoarea 4.
algoritmul va observa ca acesta nu este numarul cautat si va cauta in jumatatea unde i-l va gasi cu siguranta
adica in intervalul poziiilor 6-10, aici se va lua din nou mijlocul, unde se va gasi la pozitia 8, elementul cu numarul 7, adica exact ce cautam noi. La final, functia va returna pozitia 8, adica exact unde se gaseste elementul 7. Daca nu gasea acest element in sirul dat, se returna -1.


Atentie, acest algormitm este foarte rapid insa are partile lui rele -> necesita ca sirul(array-ul) sa fie sortat inainte de cautarea in el.