La ricerca sequenziale scorre l'array incrementando l'indice di 1
La ricerca binaria presuppone che tu abbia l'array precedentemente ordinato. Dati due indici di riferimento AB calcola C dividendo l'intervallo per 2 [(A+B)/2]. Se la comparazione è maggiore o minore sposta uno dei due indici a C+1 or C-1 e ripete fino a che A<=B.
Esempio:
array: A,B,C,D,E,F,G,H,I,J.
key=F
A=0; B=9; C=4; ==> 'E' < 'F' ==> A=5
A=5; B=9; C=7; ==> 'H' > 'F' ==> B=6
A=5; B=6; C=5: ==> 'F' == 'F'
Nei casi peggiori ?(log n)
Ho fatto delle prove su un array di interi da 100 milioni di numeri (400,000,000 bytes) per misurare i tempi peggiori nelle due ricerche.
[dicotomica]
real 0m0.650s
user 0m0.393s
sys 0m0.254s
[sequenziale]
real 0m1.415s
user 0m1.144s
sys 0m0.267s
codice utilizzato:
#include <stdio.h>
#include <stdlib.h>
#define NUM 10000000
#define SEARCH bin_search
//#define SEARCH seq_search
int cmp (const void * a, const void * b)
{
return ( *(int *)a - *(int *)b );
}
size_t seq_search (void *array, size_t num, size_t size, void *match, int (comparator)(const void *, const void *))
{
size_t i;
for (i=0;i<num;i++)
if (!comparator (array+(i*size),match))
return i;
return -1;
}
size_t bin_search (void *array, size_t num, size_t size, void *match, int (comparator)(const void *, const void *))
{
size_t start=0,end=num-1,middle;
int r;
while (start <= end)
{
middle=(start+end)/2;
if ((r=comparator (array+(middle*size),match))>0)
end=middle-1;
else if (r<0)
start=middle+1;
else
return middle;
}
return -1;
}
int main ()
{
int *arr, key;
int r;
if ((arr=(int *)malloc(sizeof (int) * NUM))==NULL)
{
fprintf (stderr,"Out of mem\n");
return -1;
}
key=NUM;
for (r=0;r<NUM;r++)
*(arr+r)=r+1;
if ((r=SEARCH (arr,NUM, sizeof (int),&key, cmp))!=-1)
printf ("%d found in pos %d\n",key,r);
else
printf ("%d not found\n",key);
free (arr);
return 0;
}