La ricerca binaria o logaritmica è un modo di trovare un elemento in una lista molto velocemente, a patto che la lista sia ordinata.
Ecco un raffronto tra la velocità di ricerca normale e quella binaria:
Come potete vedere la velocità della ricerca binaria rimane stabile con il numero di elementi di una lista, mentre una ricerca eseguita in senso classico ha un tempo di ricerca che cresce linearmente col crescere della lista.
Il problema della ricerca di tipo binario è che ha bisogno di una lista ordinata (per valore, alfabeticamente, o qualsiasi altro ordinamento).
Per questo la ricerca di tipo binario porta grandi benefici quando la lista viene modificata raramente, mentre la ricerche sono molto più frequenti; altrimenti il tempo necessario ogni volta a riordinare la lista vanifica ogni vantaggio.
Se per esempio la lista è un array di livecode, per ordinarla è necessaria questa funzione:
function sortedArray @pArray
# fetch the keys and sort them using the array entry values
get the keys of pArray
sort lines of it by pArray[each]
split it by return
# create a new sorted array using the mapped keys
put 1 into tNextIndex
repeat for each element tIndex in it
put pArray[tIndex] into tSortedArray[tNextIndex]
add 1 to tNextIndex
end repeat
return tSortedArray
end sortedArray
Una volta ordinata la ricerca binaria può avvenire con questa funzione:
function logarithmicSearch @pArray, pItem, pLeft, pRight
local tIndex
local tResult
# create a new range pointer that points to the item that lies
# right between the left and right range pointers
put round ((pLeft + pRight) / 2) into tIndex
# if we have found the matching item then stop processing and return it
if pArray[tIndex] = pItem then
put tIndex into tResult
# if any of the range pointers have the same value
# then the item we are looking for does not exist in the array and we return 0
else if (pLeft = pRight or pLeft = tIndex or pRight = tIndex) then
put 0 into tResult
# if we have not yet found a match and none of the range pointers have the same
# value then call logarithmicSearch again with a smaller search range
# we are effectively halving the search area, each time we call logarithmicSearch
else if pArray[tIndex] > pItem then
put logarithmicSearch (pArray, pItem, pLeft, tIndex) into tResult
else
put logarithmicSearch (pArray, pItem, tIndex, pRight) into tResult
end if
return tResult
end logarithmicSearch
Per chiamare la funzione bisogna indicare l'array, il valore cercato, zero e il numero di elementi dell'array, ad esempio:
put sortedArray(tArr) into tArr
put the number of lines of the keys of tArr into tnkeys
put logarithmicSearch (tArr, "testo da cercare", 0, tnkeys )
In alternativa a tutto ciò, vi ricordo che SQLite è integrato in livecode e permette delle ricerche molto veloci.
