Modulo 12 — Algoritmi
Algoritmi di Ricerca
Ricerca lineare, binaria, interpolazione, ricerca in stringhe e la libreria bsearch.
1. Ricerca Lineare — O(n)
Esamina ogni elemento dall'inizio fino a trovare il target. Funziona su qualsiasi array, ordinato o no.
CRicerca lineare — varianti
#include <stdio.h>
// Restituisce l'indice o -1 se non trovato
int ricerca_lineare(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i;
}
return -1;
}
// Trova TUTTE le occorrenze
int ricerca_tutte(int arr[], int n, int target, int risultati[], int max_ris) {
int count = 0;
for (int i = 0; i < n && count < max_ris; i++) {
if (arr[i] == target) risultati[count++] = i;
}
return count;
}
// Ricerca con predicato (funzione generica)
int trova_se(int arr[], int n, int (*predicato)(int)) {
for (int i = 0; i < n; i++) {
if (predicato(arr[i])) return i;
}
return -1;
}
int e_negativo(int x) { return x < 0; }
int e_maggiore_50(int x) { return x > 50; }
// Ricerca sentinella (mette il target alla fine → evita controllo i<n)
int ricerca_sentinella(int arr[], int n, int target) {
int ultimo = arr[n-1];
arr[n-1] = target; // sentinella
int i = 0;
while (arr[i] != target) i++;
arr[n-1] = ultimo; // ripristina
return (i < n-1 || arr[n-1] == target) ? i : -1;
}
int main() {
int arr[] = {4, 7, 2, 9, 1, 15, 7, 3, 7, 8};
int n = 10;
printf("Cerca 7: indice %d\n", ricerca_lineare(arr, n, 7));
int pos[10];
int k = ricerca_tutte(arr, n, 7, pos, 10);
printf("Tutte le posizioni di 7: ");
for (int i=0; i 50: indice %d\n", trova_se(arr, n, e_maggiore_50));
int arr2[] = {-5, 3, -8, 7, 2};
printf("Primo negativo: indice %d\n", trova_se(arr2, 5, e_negativo));
return 0;
} 2. Ricerca Binaria — O(log n)
Richiede un array ordinato. Ad ogni passo taglia a metà lo spazio di ricerca. Con N=1 miliardo → al massimo 30 comparazioni.
CBinary Search — iterativa, ricorsiva e varianti
#include <stdio.h>
#include <stdlib.h>
// Versione iterativa (preferibile: no stack overhead)
int binary_search(int arr[], int n, int target) {
int sx = 0, dx = n - 1;
while (sx <= dx) {
int mid = sx + (dx - sx) / 2; // NOTA: non (sx+dx)/2 per evitare overflow!
if (arr[mid] == target) return mid;
if (arr[mid] < target) sx = mid + 1;
else dx = mid - 1;
}
return -1;
}
// Versione ricorsiva
int binary_search_ric(int arr[], int sx, int dx, int target) {
if (sx > dx) return -1;
int mid = sx + (dx - sx) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return binary_search_ric(arr, mid+1, dx, target);
return binary_search_ric(arr, sx, mid-1, target);
}
// Lower bound: prima posizione dove arr[i] >= target
int lower_bound(int arr[], int n, int target) {
int sx = 0, dx = n;
while (sx < dx) {
int mid = sx + (dx - sx) / 2;
if (arr[mid] < target) sx = mid + 1;
else dx = mid;
}
return sx; // arr[sx] >= target, oppure sx==n se tutti < target
}
// Upper bound: prima posizione dove arr[i] > target
int upper_bound(int arr[], int n, int target) {
int sx = 0, dx = n;
while (sx < dx) {
int mid = sx + (dx - sx) / 2;
if (arr[mid] <= target) sx = mid + 1;
else dx = mid;
}
return sx;
}
// Conta occorrenze di target in array ordinato → O(log n)
int conta_occorrenze(int arr[], int n, int target) {
return upper_bound(arr, n, target) - lower_bound(arr, n, target);
}
// Trova il ceiling: più piccolo elemento >= target
int ceiling(int arr[], int n, int target) {
int pos = lower_bound(arr, n, target);
return (pos < n) ? arr[pos] : -1;
}
// Cerca il valore più vicino al target
int nearest(int arr[], int n, int target) {
int pos = lower_bound(arr, n, target);
if (pos == 0) return arr[0];
if (pos == n) return arr[n-1];
int diff_sin = target - arr[pos-1];
int diff_des = arr[pos] - target;
return diff_sin <= diff_des ? arr[pos-1] : arr[pos];
}
// bsearch: versione standard della stdlib
int cmp_int(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int n = 10;
printf("Array: ");
for(int i=0;i<n;i++) printf("%d ",arr[i]);
printf("\n\n");
printf("Cerca 7: indice %d\n", binary_search(arr, n, 7));
printf("Cerca 6: indice %d (non trovato)\n", binary_search(arr, n, 6));
// Lower/Upper bound
int arr2[] = {1, 2, 4, 4, 4, 5, 6};
int n2 = 7;
printf("\nArray: ");
for(int i=0;i<n2;i++) printf("%d ",arr2[i]);
printf("\n");
printf("lower_bound(4) = %d (prima pos. con arr>=4)\n", lower_bound(arr2,n2,4));
printf("upper_bound(4) = %d (prima pos. con arr>4)\n", upper_bound(arr2,n2,4));
printf("Occorrenze di 4: %d\n", conta_occorrenze(arr2,n2,4));
printf("\nCeiling di 4 in primo array: %d\n", ceiling(arr,n,4));
printf("Nearest di 6 in primo array: %d\n", nearest(arr,n,6));
// bsearch standard
int target = 13;
int *p = bsearch(&target, arr, n, sizeof(int), cmp_int);
printf("\nbsearch(13): %s\n", p ? "trovato" : "non trovato");
return 0;
}3. Interpolation Search — O(log log n)
Migliora la ricerca binaria quando i valori sono distribuiti uniformemente: stima la posizione del target invece di andare sempre a metà.
CInterpolation Search
#include <stdio.h>
int interpolation_search(int arr[], int n, int target) {
int sx = 0, dx = n - 1;
while (sx <= dx && target >= arr[sx] && target <= arr[dx]) {
if (sx == dx) {
return (arr[sx] == target) ? sx : -1;
}
// Formula di interpolazione: stima dove dovrebbe essere il target
// (come cercare un nome in una rubrica: vai vicino alla lettera giusta)
int pos = sx + (long long)(target - arr[sx])
* (dx - sx)
/ (arr[dx] - arr[sx]);
if (arr[pos] == target) return pos;
if (arr[pos] < target) sx = pos + 1;
else dx = pos - 1;
}
return -1;
}
int main() {
// Funziona meglio con dati uniformemente distribuiti
int arr[100];
for (int i = 0; i < 100; i++) arr[i] = i * 10; // 0, 10, 20, ..., 990
printf("Cerca 350: indice %d (valore: %d)\n",
interpolation_search(arr, 100, 350),
arr[interpolation_search(arr, 100, 350)]);
printf("Cerca 777: indice %d\n", interpolation_search(arr, 100, 777));
return 0;
}4. Ricerca in Stringhe
Trovare un pattern all'interno di un testo è uno dei problemi fondamentali dell'informatica.
CNaive Search vs KMP (Knuth-Morris-Pratt)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// O(n*m) — semplice ma lento per testi grandi
int naive_search(const char *testo, const char *pattern) {
int n = strlen(testo), m = strlen(pattern);
for (int i = 0; i <= n-m; i++) {
int j;
for (j = 0; j < m; j++) {
if (testo[i+j] != pattern[j]) break;
}
if (j == m) return i; // Trovato alla posizione i
}
return -1;
}
// Algoritmo KMP — O(n+m)
// Costruisce la tabella dei fallimenti (lps: longest proper prefix suffix)
void calcola_lps(const char *pattern, int m, int *lps) {
lps[0] = 0;
int len = 0, i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
lps[i++] = ++len;
} else {
if (len != 0) len = lps[len-1];
else lps[i++] = 0;
}
}
}
int kmp_search(const char *testo, const char *pattern) {
int n = strlen(testo), m = strlen(pattern);
int *lps = malloc(m * sizeof(int));
calcola_lps(pattern, m, lps);
int i = 0, j = 0;
while (i < n) {
if (testo[i] == pattern[j]) { i++; j++; }
if (j == m) {
int pos = i - j;
free(lps);
return pos; // Prima occorrenza
} else if (i < n && testo[i] != pattern[j]) {
if (j != 0) j = lps[j-1];
else i++;
}
}
free(lps);
return -1;
}
// Conta tutte le occorrenze di pattern in testo
int conta_occorrenze_pattern(const char *testo, const char *pattern) {
int n = strlen(testo), m = strlen(pattern), count = 0;
const char *p = testo;
while ((p = strstr(p, pattern)) != NULL) {
count++;
p += m;
}
return count;
}
int main() {
const char *testo = "Il programma C e' un linguaggio di programmazione C classico.";
const char *pattern = "C";
printf("Testo: %s\n", testo);
printf("Pattern: %s\n\n", pattern);
int pos_naive = naive_search(testo, pattern);
int pos_kmp = kmp_search(testo, pattern);
printf("Naive: prima occorrenza a posizione %d\n", pos_naive);
printf("KMP: prima occorrenza a posizione %d\n", pos_kmp);
printf("strstr: conferma posizione %ld\n", (long)(strstr(testo, pattern) - testo));
printf("Totale occorrenze di \"%s\": %d\n",
pattern, conta_occorrenze_pattern(testo, pattern));
return 0;
}5. Ricerca su Strutture Dati
CRicerca in albero binario di ricerca (BST)
#include <stdio.h>
#include <stdlib.h>
typedef struct Nodo {
int val;
struct Nodo *sx, *dx;
} Nodo;
Nodo* nuovo(int v) {
Nodo *n = malloc(sizeof(Nodo));
n->val = v; n->sx = n->dx = NULL;
return n;
}
// Inserimento in BST
Nodo* inserisci(Nodo *radice, int v) {
if (!radice) return nuovo(v);
if (v < radice->val) radice->sx = inserisci(radice->sx, v);
else if (v > radice->val) radice->dx = inserisci(radice->dx, v);
return radice;
}
// Ricerca in BST — O(log n) se bilanciato, O(n) nel caso peggiore
Nodo* cerca(Nodo *radice, int target) {
if (!radice || radice->val == target) return radice;
if (target < radice->val) return cerca(radice->sx, target);
return cerca(radice->dx, target);
}
// Minimo e massimo
Nodo* minimo(Nodo *n) { while (n->sx) n = n->sx; return n; }
Nodo* massimo(Nodo *n) { while (n->dx) n = n->dx; return n; }
// Predecessor (il più grande valore minore di target)
int predecessor(Nodo *radice, int target) {
Nodo *pred = NULL, *curr = radice;
while (curr) {
if (curr->val < target) { pred = curr; curr = curr->dx; }
else curr = curr->sx;
}
return pred ? pred->val : -1;
}
void stampa_inorder(Nodo *n) {
if (!n) return;
stampa_inorder(n->sx);
printf("%d ", n->val);
stampa_inorder(n->dx);
}
int main() {
int valori[] = {50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45};
Nodo *bst = NULL;
for (int i=0; i<11; i++) bst = inserisci(bst, valori[i]);
printf("BST in-order: ");
stampa_inorder(bst);
printf("\n");
int cerca_val = 40;
Nodo *trovato = cerca(bst, cerca_val);
printf("Cerca %d: %s\n", cerca_val, trovato ? "trovato" : "non trovato");
printf("Minimo: %d\n", minimo(bst)->val);
printf("Massimo: %d\n", massimo(bst)->val);
printf("Predecessor di 50: %d\n", predecessor(bst, 50));
return 0;
}🏋️ Esercizi
Metti alla prova le tecniche di ricerca.
1
Implementa una ricerca binaria generica simile a bsearch della stdlib: my_bsearch(key, base, n, size, cmp). Usala per cercare: un intero in array di int, una stringa in array di stringhe, una struct per un campo chiave.
C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void* my_bsearch(const void *key, const void *base, int n,
size_t size, int (*cmp)(const void*, const void*)) {
int sx = 0, dx = n-1;
const char *arr = base;
while (sx <= dx) {
int mid = (sx+dx)/2;
int r = cmp(key, arr + mid*size);
if (r == 0) return (void*)(arr + mid*size);
if (r > 0) sx = mid+1;
else dx = mid-1;
}
return NULL;
}
int cmp_int(const void *a, const void *b) { return *(int*)a - *(int*)b; }
int cmp_str(const void *a, const void *b) { return strcmp((char*)a, *(char**)b); }
typedef struct { char nome[30]; int codice; } Prodotto;
int cmp_prodotto(const void *a, const void *b) {
return ((Prodotto*)a)->codice - ((Prodotto*)b)->codice;
}
int main() {
int numeri[] = {1,3,5,7,9,11,13,15};
int target = 9;
int *r1 = my_bsearch(&target, numeri, 8, sizeof(int), cmp_int);
printf("Cerca %d: %s\n", target, r1 ? "trovato" : "no");
char *parole[] = {"alpha","beta","gamma","delta"};
qsort(parole, 4, sizeof(char*), (int(*)(const void*,const void*))strcmp);
char *chiave = "gamma";
char **r2 = my_bsearch(chiave, parole, 4, sizeof(char*), cmp_str);
printf("Cerca '%s': %s\n", chiave, r2 ? "trovato" : "no");
Prodotto prod[] = {{.nome="Laptop",.codice=100},{.nome="Mouse",.codice=200},{.nome="Tast",.codice=300}};
Prodotto cerca = {.codice=200};
Prodotto *r3 = my_bsearch(&cerca, prod, 3, sizeof(Prodotto), cmp_prodotto);
if (r3) printf("Prodotto codice 200: %s\n", r3->nome);
return 0;
}2
Dato un array ordinato con possibili duplicati, trova la prima e ultima posizione di un elemento target in O(log n). Es: [1,2,4,4,4,5,6] cerca 4 → prima=2, ultima=4. Se non esiste → [-1, -1].
C
#include <stdio.h>
int prima_occorrenza(int arr[], int n, int t) {
int sx=0, dx=n-1, risultato=-1;
while(sx<=dx) {
int mid=(sx+dx)/2;
if(arr[mid]==t) { risultato=mid; dx=mid-1; } // Continua a sinistra
else if(arr[mid]<t) sx=mid+1;
else dx=mid-1;
}
return risultato;
}
int ultima_occorrenza(int arr[], int n, int t) {
int sx=0, dx=n-1, risultato=-1;
while(sx<=dx) {
int mid=(sx+dx)/2;
if(arr[mid]==t) { risultato=mid; sx=mid+1; } // Continua a destra
else if(arr[mid]<t) sx=mid+1;
else dx=mid-1;
}
return risultato;
}
int main() {
int arr[] = {1,2,4,4,4,5,6};
int n=7, target=4;
printf("Array: 1 2 4 4 4 5 6\n");
printf("Target %d: prima=%d, ultima=%d, count=%d\n",
target,
prima_occorrenza(arr,n,target),
ultima_occorrenza(arr,n,target),
ultima_occorrenza(arr,n,target)-prima_occorrenza(arr,n,target)+1);
return 0;
}3
Data una matrice NxM dove ogni riga e ogni colonna è ordinata in modo crescente, trova se un valore esiste in O(n+m). Inizia dall'angolo in alto a destra: se il valore è maggiore del target vai a sinistra, se minore scendi in basso.
C
#include <stdio.h>
#define N 4
#define M 4
int cerca_in_matrice(int mat[N][M], int target, int *riga, int *col) {
int r=0, c=M-1; // Angolo in alto a destra
while (r < N && c >= 0) {
if (mat[r][c] == target) { *riga=r; *col=c; return 1; }
if (mat[r][c] > target) c--; // Il target è a sinistra
else r++; // Il target è in basso
}
return 0;
}
int main() {
int mat[N][M] = {
{ 1, 4, 7, 11},
{ 2, 5, 8, 12},
{ 3, 6, 9, 16},
{10, 13, 14, 17}
};
printf("Matrice:\n");
for(int i=0;i<N;i++){for(int j=0;j<M;j++) printf("%4d",mat[i][j]); printf("\n");}
int r,c;
int valori[]={5,9,7,15};
for(int i=0;i<4;i++){
int found=cerca_in_matrice(mat,valori[i],&r,&c);
if(found) printf("Cerca %2d: trovato a [%d][%d]\n",valori[i],r,c);
else printf("Cerca %2d: non trovato\n",valori[i]);
}
return 0;
}