Questo spunto l’ho preso sfogliando un mio vecchio libro che tratta di “trucchi” per VB6, il progenitore di VBA, scritto da Francesco Balena. La raccolta di trucchi è vasta e attuale, oltre che riproducibile in VBA a volte con piccoli adattamenti.
In questo articolo parliamo di un semplice algoritmo di ricerca binaria. Se un vettore è già ordinato, è possibile effettuare molto rapidamente una ricerca tra i suoi elementi utilizzando l’algoritmo di ricerca binaria (binary search), più efficiente della ricerca lineare o sequenziale, che consiste in un semplice ciclo che confronta il valore cercato con tutti gli elementi del vettore. La routine funziona con vettori di tipo numerico o stringa, ordinati sia in senso ascendente che discendente. Il confronto tra stringhe avviene in modo case-sensitive (ma la modifica è banale). L’argomento opzionale last_item è l’indice dell’ultimo elemento che deve essere ordinato, ed è utile se il vettore è riempito solo parzialmente.
Option Explicit
Function binary_search(arr As Variant, search As Variant, Optional last_item As Variant) As Long
Dim index As Long, first As Long, last As Long
Dim middle As Long, inverse_order As Boolean
'gestisce il paramtero opzionale
If IsMissing(last_item) Then last_item = UBound(arr)
first = LBound(arr)
last = last_item
'deduce la direzione dell'ordinamento
inverse_order = (arr(first) > arr(last))
binary_search = first - 1
Do
middle = (first + last) \ 2
If arr(middle) = search Then
binary_search = middle
Exit Do
ElseIf ((arr(middle) < search) Xor inverse_order) Then
first = middle + 1
Else
last = middle - 1
End If
Loop Until first > last
End Function
Si possono migliorare le prestazioni della routine se si conosce il tipo degli elementi del vettore ordinato. Basta modificare la prima riga del codice. Ad esempio, la modifica che sgeue agisce solo con vettori di Long:
Function binary_search(arr As Long, search As Variant, Optional last_item As Variant) As Long
› Ricerca binaria VBA