Ricerca binaria

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.