Algoritmi di Ricerca

Nella programmazione è importante conoscere gli algoritmi di ricerca ed avere dimestichezza con essi, poiché in certe occasioni è necessario risolvere problemi legati al recuperare informazioni da strutture come array o record. Una ricerca in un piccolo insieme di valori avviene sequenzialmente, ma se dobbiamo ricercare un numero di telefono in un elenco abbiamo la necessità che questi sia ordinato in una qualche maniera, difatti i passi che compiamo sono:

• apriamo l’elenco telefonico contenente gli abbonati di una determinata città
• verifichiamo in alto le iniziali dei nomi della pagina con quello che stiamo cercando
• vado avanti o indietro nelle pagine alfabeticamente fino a che non  trovo la pagina con il nominativo da me ricercato e leggo il valore

Lo stesso procedimento viene effettuato nella ricerca di un vocabolo in un dizionario, in quanto anch’esso è organizzato logicamente in ordine alfabetico. Un aspetto importante da considerare è la certezza o no che l’elemento ricercato sia nell’elenco e quindi gli algoritmi di ricerca si suddividono in due gruppi principali: algoritmi di ricerca certa ed algoritmi di ricerca incerta.
Il caso più semplice di ricerca è quella lineare, niente altro che iterare su tutti gli elementi dell’array e terminare quando abbiamo trovato l’elemento.

#include “stdio.h”

void main()
{
    int iArrVal[] = {12, 65, 2, 5, 54, 98, 23, 123, 14, 76};
    int i;
    int iSearch = 123;
    int bFound = 0;

    for (i = 0; i < sizeof(iArrVal) / sizeof(int); i++)
    {
          if (iSearch == iArrVal[i])
         {
                printf(“Abbiamo trovato il numero %d nell’elemento %d\n”, iSearch, i$
                bFound = 1;
                break;
          }
    }

    if (!bFound)
    {
         printf(“La ricerca ha avuto esito negativo\n”);
    }
}

Questo esempio è molto semplice, ma rende bene l’idea di come si effettuano le ricerche lineari. Un altro algoritmo che si usa su elenchi di valori ordinati è quello della ricerca binaria:

• si confronta l’elemento da ricercare con il valore situato in mezzo alla lista
• se i due elementi sono uguali la ricerca termina positivamente
• se l’elemento da ricercare è minore di quello di mezzo la ricerca prosegue dal punto 1 nella prima metà del vettore
• se l’elemento è maggiore di quello di mezzo, la ricerca prosegue dal punto 1 nella seconda metà dell’array

Questo è il caso di un array ordinato in senso crescente. Ad ogni ciclo, quindi si dimezza il numero di elementi su cui operare la ricerca. Ovviamente si può applicare questo algoritmo solo se si conosce la dimensione della struttura in partenza, altrimenti non è possibile risalire all’elemento centrale. Il ciclo deve continuare finché non si arriva a due elementi.

#include “stdio.h”

void swap(int* iArr, int iOld, int iNew)
{
    int iTemp;

    if (iArr == NULL)
       return;

    iTemp = iArr[iOld];
    iArr[iOld] = iArr[iNew];
    iArr[iNew ] = iTemp;
}

void ordina(int* iArr, int iNum)
{
     int i;
     int k = 1;
     int bSwap = 0;

     if (iArr == NULL)
         return;

     while (1)
     {
           bSwap = 0;
           for (i = 0; i < iNum – k; i++)
          {
                if (iArr[i] > iArr[i + 1])
               {
                     swap(iArr, i + 1, i);
                     bSwap = 1;
               }
          }

          if (bSwap > 0)
         {
             &nbs
p; bSwap = 0;
               k++;
               if (k >= iNum – 1)
                     break;
          }
          else
              break;
      }
}

void main()
{
      int iArrVal[] = {12, 65, 2, 5, 54, 98, 23, 123, 14, 76};
      int i, iMedio;
      int iSearch = 123;
      int bFound = 0;
      int iNum = sizeof(iArrVal) / sizeof(int);

      ordina(iArrVal, iNum);

       iMedio = iNum / 2;
       do
       {
             if (iArrVal[iMedio – 1] == iSearch)
            {
                 printf(“L’elemento si trova in posizione %d\n”, iMedio);
                 bFound = 1;
                 break;
            }
            else if (iSearch > iArrVal[iMedio – 1])
            {
                 iMedio += iNum;
            }

            iMedio /= 2;

            if (iNum – iMedio == 1)
           {
                  if (iArrVal[iNum – 1] == iSearch)
                 {
                        printf(“L’elemento si trova in posizione %d\n”, iNum);
                        bFound = 1;
                  }
                  break;
            }
      }
      while (iMedio > 0 && iMedio < iNum);

       if (!bFound)
      {
             printf(“La ricerca ha avuto esito negativo\n”);
      }
}

In questo esempio ordino i dati dell’array secondo i dettami imparati nell’articolo sull’ordinamento e poi calcolo il punto medio dell’array e verifico, purtroppo l’ultimo elemento dà dei problemi perché la divisione di 19 è sempre 9 e quindi va in loop, allora ho inserito un break se l’ultimo elemento è uguale al valore cercato.