La belleza de las Búsquedas Binarias

A continuación encontrarás traducido al castellano el artículo escrito por Kem Tekinay y publicado originalmente en el Blog oficial de Xojo.

Descripción del problema: necesitas buscar en un array para ver si contiene un valor en concreto. La solución sencilla consiste en usar IndexOf si se trata de un array simple, o bien mediante un bucle como este:

for each item as ArrayType in myArray
  if item.Matches( myValue ) then
    YesSiree( myValue )
    exit
  end if
next

Muy sencillo, pero ¿qué ocurre si el array es realmente grande? ¿y si además has de repetir esta operación varias veces?

Por ejemplo, digamos que tu array contiene 20.000 elementos. Por cada valor que no coincida tu código tendrá que realizar 10.000 comparaciones. Pero si se puede ordenar el array, entonces podrás realizar dicha tarea en, como máximo, 14 comparaciones utilizando para ello una comparación binaria.

El concepto es simple: partes de una lista ordenada y empiezas en la mitad. Si lo que estás intentando encontrar es inferior en dicho punto, entonces podrás descartar la mitad superior de la lista; de modo que comenzarás de nuevo en la mitad del resto. Al recortar por la mitad de forma continua la lista, realizarás como máximo Ceil(Log2(arrayCount)) comparaciones por valor.

Para simplificar, digamos que quieres buscar en un array de cadenas. (De acuerdo, un Diccionario podría ser una mejor opción en este caso, pero aquí se trata de mostrar el ejemplo). El código sería similar al siguiente:

myArray.Sort
 
var firstIndex as integer = 0
var lastIndex as integer = myArray.LastIndex
 
while firstIndex <= lastIndex
  var midPoint as integer = ( lastIndex - firstIndex ) \ 2 + firstIndex
 
  var compare as string = myArray( midPoint )
 
  if myValue = compare then
    YesSiree( myValue )
    exit
  end if
 
  if myValue < compare then
    lastIndex = midPoint - 1
  else
    firstIndex = midPoint + 1
  end if
wend

Con este array de 10.000 elementos la primera iteración del bucle comprobaría el item en la posición 5.000. Si myValue es superior, entonces miraría en el ítem 7.500. ¿Aún más grande? Entonces ahora mirará en el item 8.750, etc. El array completo se procesará de forma eficiente sin necesidad de comprobar cada uno de los valores. Si tienes que hacer esto con 10.000 valores distintos, entonces terminarías como máximo con 14.000 comparaciones en vez de 10 millones de comparaciones.

En definitiva un ahorro importante, ¿verdad?