Ricerca lineare
Vi è una grande differenza tra cercare fra dati non ordinati e cercare entro un insieme di dati ordinati.

Se si deve cercare un numero in una sequenza di valori che si presentano in ordine arbitrario, non si può fare nulla per accelerare la ricerca.

Si devono semplicemente scorrere tutti gli elementi, esaminandoli uno ad uno, fino a quando si trova una corrispondenza oppure si arriva in fondo all'elenco.

Questa ricerca si chiama lineare o sequenziale.

 

 Il programma LinearSearch

Ecco un programma che implementa la ricerca lineare attraverso un array a di numeri interi per trovare il valore v. La procedura alla fine restituisce l'indice della corrispondenza oppure -1 se v non è presente in a.

public class LinearSearch
{ 
    public static void main(String[] args)
    {  
        ConsoleReader console = new ConsoleReader(System.in);
        int[] a = ArrayUtil.randomIntArray(20, 100);
        ArrayUtil.print(a);
        System.out.println("Immettere il numero da cercare:");
        int n = console.readInt();
        int j = search(a, n);
        System.out.println("Trovato nella posizione " + j);
    }

    /**
    Trova un valore in un array con la ricerca lineare.
    @param a l'array 
    @param v il valore da cercare
    @return l'indice nel quale si trova il valore,
    oppure -1 se non è presente nell'array
    */
    public static int search(int[] a, int v)
    {  
        for (int i = 0; i < a.length; i++)
            { if (a[i] == v)  return i;}
        return -1;
    }
}

 

Ricerca binaria

Supponiamo ora di cercare un elemento in un array di interi che è stato precedentemente ordinato. Consideriamo ad esempio il seguente array:

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]
 14   43   76 100 115  290  500  511

e supponiamo di voler cercare il valore 123. L'ultimo valore nella prima metà dell'array (a[3]=100) è minore del valore cercato, quindi dovremo cercare la corrispondenza nella seconda metà dell'array:

a[4] a[5] a[6] a[7]
115 290 500 511

L'ultimo valore della prima metà di questa sequenza (a[5]=290) è maggiore del valore cercato, quindi dovremo cercare la corrispondenza nella prima metà

a[4] a[5]
115 290

L'ultimo valore della prima metà di questa sequenza (a[4]=115) è minore del valore cercato, quindi dobbiamo esaminare la seconda metà:

a[5]
290

Ora possiamo constatare che non abbiamo una corrispondenza poiché 123 è diverso da 290.

Questo processo di ricerca si chiama ricerca binaria.

 

 

 


Il programma BinarySearch

Ecco un programma che implementa la ricerca binaria in un array a di numeri interi ordinati per trovare il valore v. La procedura alla fine restituisce l'indice della corrispondenza oppure -1 se v non è presente in a.

public class BinarySearch
{ 
    public static void main(String[] args)
    { 
        ConsoleReader console = new ConsoleReader(System.in);

        // costruisce un array casuale e lo ordina
        int[] a = ArrayUtil.randomIntArray(20, 100);
        SelSort.sort(a);

        ArrayUtil.print(a);
        System.out.println("Immettere il numero da cercare:");
        int n = console.readInt();
        int j = search(a, n);
        System.out.println("Trovato nella posizione " + j);
    }
    /**
    Trova un valore entro un array ordinato con la ricerca binaria.
    @param a un array ordinato
    @param from il primo indice nell'intervallo in cui cercare
    @param to l'ultimo indice nell'intervallo in cui cercare
    @param v il valore da cercare
    @return l'indice nel quale si trova il valore,
    oppure -1 se non è presente nell'array
    */
    public static int binarySearch(int[] a, int from, int to, int v)
    { 
        if (from > to)   return -1;
        int mid = (from + to) / 2;
        int diff = a[mid] - v;
        if (diff == 0)     // a[mid] == v
                return mid;
        else if (diff < 0)     // a[mid] < v 
                    return binarySearch(a, mid + 1, to, v);
                else
                    return binarySearch(a, from, mid - 1, v);
     }
     /**
    Trova un valore in un array ordinato con la ricarca binaria.
    @param a l'array ordinato
    @param v il valore da cercare
    @return l'indice nel quale si trova il valore, oppure -1
     */
    public static int search(int[] a, int v)
    { 
        return binarySearch(a, 0, a.length - 1, v); 
    }
}

 

 

 


Prestazioni degli algoritmi di ricerca
Supponiamo che l'array a contenga n elementi.

  • Quanto tempo occorre per eseguire una ricerca lineare?

    Se supponiamo che l'elemento cercato sia presente nell'array, in media l'algoritmo di ricerca lineare visita n/2 elementi. Se non è presente, vanno ispezionati tutti gli n elementi dell'array.

  • Quanto tempo occorre per eseguire una ricerca binaria?

    In questo caso, per eseguire una ricerca sono necessarie al più log n +1 visite degli elementi dell'array.

Dunque, se si devono eseguire molte ricerche su uno stesso array, conviene prima ordinarlo e poi usare l'algoritmo di ricerca binaria.