Ricerca binaria
Ultimo aggiornamento
La ricerca binaria trova un valore in un array **ordinato** dimezzando ripetutamente la finestra di ricerca. Confronta l'elemento centrale con il valore cercato: se coincidono, la ricerca finisce; altrimenti scarta la metà che non può contenere il valore e la finestra si riduce all'altra metà. Ogni confronto elimina metà degli elementi rimasti, ed è per questo che richiede O(log n): cercare in un milione di valori ordinati richiede al massimo circa 20 confronti.
L'animazione qui sopra mostra i puntatori lo, mid e hi e oscura la metà eliminata dopo ogni confronto. L'unica condizione irrinunciabile: l'array deve essere già ordinato. Su dati non ordinati ti serve la ricerca lineare oppure prima un ordinamento (vedi merge sort). La stessa idea di dimezzamento è alla base dell'albero binario di ricerca.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(1) | L'elemento centrale è quello cercato al primo confronto. |
| Caso medio | O(log n) | Ogni confronto dimezza la finestra rimasta. |
| Caso peggiore | O(log n) | La finestra si riduce a un solo elemento prima di trovarlo o mancarlo. |
| Spazio | O(1) | La versione iterativa tiene solo gli indici lo, hi e mid. |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Imposta lo al primo indice e hi all'ultimo indice dell'array ordinato. |
| 2 | Calcola l'indice centrale: mid = (lo + hi) // 2. |
| 3 | Se a[mid] è uguale al valore cercato, restituisci mid (trovato). |
| 4 | Se a[mid] è **minore** del valore cercato, questo può stare solo nella metà destra: imposta lo = mid + 1. |
| 5 | Se a[mid] è **maggiore** del valore cercato, cerca nella metà sinistra: imposta hi = mid - 1. |
| 6 | Ripeti dal passo 2 finché lo <= hi; se la finestra si svuota, il valore non è nell'array. |
Esempio svolto
Ricerca di 5 in [1, 2, 3, 5, 7, 8, 9]:
| Passata | Finestra (lo..hi) | mid | a[mid] | Azione |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5: valore trovato all'indice 3. |
Una ricerca a vuoto, passo dopo passo
Cercare 4 nello stesso array mostra come la finestra si svuota:
| Passata | Finestra (lo..hi) | mid | a[mid] | Azione |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4: cerca nella metà sinistra, hi = 2. |
| 2 | 0..2 | 1 | 2 | 2 < 4: cerca nella metà destra, lo = 2. |
| 3 | 2..2 | 2 | 3 | 3 < 4, quindi lo diventa 3 e la finestra si svuota: non trovato. |
Quando usare la ricerca binaria
| Usala quando | Evitala quando |
|---|---|
| I dati sono già ordinati (o li cerchi molte volte) | I dati non sono ordinati e li cerchi una sola volta (ordinarli prima costa O(n log n)) |
| La collezione supporta un accesso casuale veloce (array) | Hai solo accesso sequenziale (liste concatenate) |
L'insieme di dati è grande (O(log n) dà il meglio su larga scala) | L'insieme di dati è minuscolo (una semplice scansione è altrettanto veloce e più semplice) |
Codice Binary Search
Un'implementazione di Binary Search pulita ed eseguibile in Python, JavaScript, Java, C++, C, Pseudocode. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Binary Search in Python
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Codice Binary Search in JavaScript
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Codice Binary Search in Java
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Codice Binary Search in C++
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Codice Binary Search in C
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Codice Binary Search in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger, search the right half26 lo ← mid + 127 ELSE28 // Target is smaller, search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)Domande frequenti sulla ricerca binaria
Qual è la complessità temporale della ricerca binaria?
O(log n) nel caso medio e peggiore, perché ogni confronto dimezza la finestra di ricerca rimasta, e O(1) nel caso migliore, quando il primo elemento centrale è quello cercato. La versione iterativa usa O(1) di spazio extra.Perché la ricerca binaria richiede un array ordinato?
Il dimezzamento si basa sull'ordine: confrontare il valore cercato con l'elemento centrale ti dice quale metà scartare solo se tutto ciò che sta a sinistra del centro è più piccolo e tutto ciò che sta a destra è più grande. Su dati non ordinati questa deduzione non vale, quindi usa la ricerca lineare oppure ordina prima.
Qual è la differenza tra ricerca binaria e ricerca lineare?
La ricerca lineare scorre gli elementi uno a uno (
O(n)) e funziona su qualsiasi array; la ricerca binaria dimezza la finestra di ricerca di un array ordinato (O(log n)) ma richiede un input ordinato. Con pochi elementi la differenza è trascurabile; su larga scala la ricerca binaria vince nettamente.Quanti confronti servono alla ricerca binaria?
Al massimo circa
log2(n) + 1: 10 confronti coprono 1.000 elementi, 20 confronti ne coprono 1.000.000. Questa crescita logaritmica è ciò che la rende la ricerca predefinita sui dati ordinati.Qual è il classico bug di overflow nella ricerca binaria?
Calcolare il centro come
(lo + hi) / 2 può causare un overflow con gli interi a dimensione fissa quando lo + hi supera il massimo del tipo. La forma sicura è mid = lo + (hi - lo) / 2. In Python non importa (gli interi hanno precisione arbitraria), ma in Java/C/C++ è un bug reale e famoso.La ricerca binaria è la stessa cosa di un albero binario di ricerca?
Condividono l'idea del dimezzamento ma hanno una struttura diversa: la ricerca binaria è un algoritmo su un array ordinato, mentre un albero binario di ricerca è una struttura dati collegata che mantiene le chiavi ordinate, così le ricerche scendono a sinistra o a destra a ogni nodo.
Risorse correlate
Altre visualizzazioni
