Recerca binari

De Wikipedia, le encyclopedia libere
Saltar a: navigation, cercar

In informatica, le recerca binari (in anglese binary search) es un algorithmo de recerca que individua le indice de un determinate valor presente in un ensemble ordinate de datos. Le recerca binari demanda un accesso casual al datos in le quales cercar.

Costo del algorithmo[modificar | modificar fonte]

Iste algorithmo cerca un elemento al interior de un array ordinate effectuante mediemente minus comparationes que un recerca sequential, e dunque plus rapidemente que isto.

Le recerca binari non usa jammais plus de \lceil\log_2 N\rceil (logarithmo base 2 de N approximate pro excesso) comparationes pro un search hit o un search miss. Totevia, a minus que non se controla a omne iteration le valores del duo indices extreme, le recerca binari emplea de facto sempre le mesme tempore super un mesme array pro cercar elementos anque in positiones diverse; le recerca sequential in vice passa desde O(n) como caso pejor a O(n/2) in le caso medie, usque a O(1) si le elemento se trova in prime position. (vide Grande O)

Analyse del algorithmo[modificar | modificar fonte]

Exemplo: recerca del elemento 4 in un collection ordinate de novem elementos.

Le algorithmo es simile al methodo usate pro trovar un parola super le dictionario: sapente que le vocabulario es ordinate alphabeticamente, le idea es de initiar le recerca non ab le prime elemento, ma ab le central, i.e. a medietate del dictionario. On compara iste elemento con le cercate:

  • si corresponde, le recerca termina indicante que le elemento ha essite trovate;
  • si es inferior, le recerca se repete super le elementos precedente (o plus tosto super le prime medietate del dictionario), eliminante le successives;
  • si in vice es superiore, le recerca se repete super le elementos successive (o plus tosto super le secunde medietate del dictionario), eliminante le precedentes.

Quando tote le elementos ha essite eliminate, le recerca termina indicante que le valor non ha essite trovate.

Implementationes[modificar | modificar fonte]

Seque un implementation, sempre in linguage C del mesme algorithmo. Hic non veni utilisate le esser recurrente dunque le function resulta plus efficiente.

 int recercaBinariNonRecursive(int lista[], int n, int x)
 {	int p,u,m;
   	p = 0;
   	u = n-1;
   	while(p<=u)
   	{	m = (p+u)/2;
        	if(lista[m]==x) 
            	return m; // valor x trovate al position m
        	else
			if(lista[m]<x)
            		p = m+1;
        		else
            		u = m-1;
    	}
    	// si le programma arriva a iste puncto, significa que 
    	// le valor x non es presente in lista, ma si il esseva,  
    	// deberea se trovar al position u (nota que hic p > u)
    	return -1;
 }

Parametros del function: lista es le array de numeros integre super le qual nos vole conducer le recerca, n es le numero del elementos presente in le array e x es le valor de cercar. Durante le execution le variabiles p e u, que illos puncta initialmente al elementos extreme del array, se approcha progressivemente restringente sempre plus le zona ubi se suppone que sia presente le valor cercate x.

E isto es un implementation recursive in Java:

public class BinarySearch {
	public int binarySearch (int a[], int p, int r, int k) {
		int q, s = -1;
		if (p <= r) {
			q = (p+r)/2;
			if (k < a[q])
				s = binarySearch(a, p, q-1, k);
			if (k > a[q])
				s = binarySearch(a, q+1, r, k);
			if (k == a[q])
				return q;
		}
		else
			return -1;
	}
}

ubi le methodo binarySearch del classe BinarySearch recipe in ingresso obviemente un array, duo indices cardine e le elemento de recercar.

Seque un implementation del algorithmo multo simile al precedentes ma in un differente linguage, C#.

Isto es un implementation sin recurrentia.

/* Function pro Recerca Binari sin recurrentia */
 int Binary_Search(int []array, int elemento)  
 {
     int start = 0, end = array.length - 1, centro = 0;
     while (start <= end)
     {
         centro = (start + end) / 2;
         if (elemento < array[centro])
             end = centro - 1;
         else
             if (elemento > array[centro])
                 start=centro+1;
             else
                 return centro; //Caso: elemento==array[centro]
     }
     return -1;
 }

Con recurrentia linguage C#:

/* Function pro Recerca Binari con recurrentia */
 int BinSe_ri(int[] arr, int n, int start, int end)
 {
     if (start > end)
         return -1;
     int middle = (start + end) / 2;
     if (n < arr[middle]) 
        return BinSe_ri(arr, n, start, middle - 1);
     if (n > arr[middle]) 
        return BinSe_ri(arr, n, middle + 1, end);
     else
        return middle;
 }
Logo

Iste pagina usa contento del Wikipedia in italiano. Le articulo original se trova a it:Ricerca binaria, e es usate secundo le mandatos del licentia de Wikipedia.