Recerca binari

De Wikipedia, le encyclopedia libere

In informatica, le recerca binari (in anglese binary search) es un algorithmo de recerca qui cerca le indice de un valor determinate presente in un insimul 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 arragiamento ordinate effectuante mediemente minus comparationes que un recerca sequential, e dunque plus rapidemente que isto.

Le recerca binari non usa jammais plus de (logarithmo base 2 de N approximate pro excesso) comparationes pro trovar le valor cercate (un search hit) o non trovar lo (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 arragiamento pro cercar elementos anque in positiones diverse; le recerca sequential in vice passa ab 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 nove 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, sed ab le elemento central, i.e. a medietate del dictionario. On compara iste elemento con lo cercate:

  • si le elementos corresponde, le recerca se termina indicante que le elemento ha essite trovate;
  • si le elemento cercate es inferior a lo a comparar, le recerca se repete super le elementos precedente (o plus tosto super le prime medietate del dictionario), eliminante le successives;
  • si al contrario le elemento es superior a lo a comparar, 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 se termina indicante que le valor non ha essite trovate.

Implementationes[modificar | modificar fonte]

Infra es un implementation, sempre in linguage C, del mesme algorithmo. Hic illo non veni usate lo qui es 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 arragiamento de numeros integre super le qual nos vole conducer le recerca, n es le numero del elementos presente in le arragiamento e x es le valor de cercar. Durante le execution le variabiles p e u, que illos puncta initialmente al elementos extreme del arragiamento, 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 arragiamento, duo indices cardine e le elemento de recercar.

Infra es un implementation del algorithmo multo simile al precedentes sed in 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 in 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;
 }
Nota
Nota