Esercizi su Vettori:
- Ricerca di un elemento in un vettore, codice della ricerca lineare:
[cpp]
/*
input: un vettore v di al massimo N elementi
un intero x
un intero n <=N.
output: k in [0,n) tale che v[k] = x
-1 se x non appartiene a v
*/
int linear_search(int v[N], int n, int x)
{
for (int i=0; i<n; i++)
if (v[i] == x) return i;
return -1;
}
[/cpp]
Algoritmo di ricerca binaria, o dicotomica (o metodo di bisezione):
[cpp]
/*
input: un vettore v di al massimo N elementi
v e’ ordinato in modo crescente
un intero x
due interi low, hi, con low < hi <=N.
output: k in [low,hi) tale che v[k] = x
-1 se x non appartiene a v
*/
int binary_search(int v[N], int low, int hi, int x)
{
if (x < v[low] || x > v[hi]) return -1;
while (low < hi) {
int mid = (low + hi)/2;
// printf("debug: search in [%d,%d,%d)\n",low,mid,hi);
if (v[mid] == x) return mid;
else if (x > v[mid]) low = mid+1;
else if (x < v[mid]) hi = mid;
}
return -1;
}
[/cpp]