-
/**
-
* @class BinarySearchUtils
-
* @author Joan Garnet
-
* @version 1.0
-
* @license http://creativecommons.org/licenses/by-sa/1.0/
-
* @date Sun Dec 18 06:56:26 2005
-
* @usage var arr:Array = [5,2,8,7,65,12,10,9,6,4,6,7,8,2,1,3,6,9,12,54,65,78,7,5,4,6];
-
* arr.sort (Array.NUMERIC);
-
* trace (arr);
-
* var index:Number = com.joangarnet.utils.BinarySearchUtils ( arr, 6 );
-
* trace (index)
-
* trace (arr[index])
-
*
-
* var arr:Array = ["apple","orange","apple","nectarine","lemon","apple"];
-
* arr.sort ();
-
* trace (arr);
-
* var index:Number = com.joangarnet.utils.BinarySearchUtils ( arr, "apple" );
-
* trace (index)
-
* trace (arr[index])
-
*/
-
class com.joangarnet.utils.BinarySearchUtils
-
{
-
/**
-
* Busca la coincidencia de [terminoBusqueda] en [arrayDeBusqueda] con índice menor
-
* binarySearch basado en la implementación en Java de Tim Bray ( http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary )
-
*
-
* @param arrayDeBusqueda: (Array) de Strings o Numbers ordenado
-
* @param terminoBusqueda: (Number) o un String
-
* @param key: (String). Corresponde a la clave en la que buscar si se trata de un array asociativo
-
* @return Devuelve -1 si no se ha encontado la coincidencia o, si se ha encontrado, la posición
-
* en el Array donde se encuentra (la de índice menor en el caso que esté repetida)
-
*/
-
static public function binarySearch ( arrayDeBusqueda:Array, terminoBusqueda:Object, key:String ):Number
-
{
-
var alto:Number = arrayDeBusqueda.length;
-
var medio:Number;
-
var bajo:Number = -1;
-
while ((alto - bajo)> 1)
-
{
-
medio = Math.floor ((alto + bajo) / 2);
-
if (key==undefined) var arrValue=arrayDeBusqueda[medio]; else var arrValue = arrayDeBusqueda[medio][key];
-
if (arrValue <terminoBusqueda)
-
{
-
bajo = medio;
-
}
-
else
-
{
-
alto = medio;
-
}
-
}
-
if (key==undefined) var arrValue=arrayDeBusqueda[alto]; else var arrValue = arrayDeBusqueda[alto][key];
-
if (alto == arrayDeBusqueda.length or arrValue != terminoBusqueda)
-
{
-
return -1;
-
}
-
else
-
{
-
return alto;
-
}
-
}
-
-
/**
-
* Busca la coincidencia parcial de [terminoBusqueda] en [arrayDeBusqueda.substr(0,terminoBusqueda.length)] con índice menor
-
*
-
* @param arrayDeBusqueda: (Array) de Strings ordenado
-
* @param terminoBusqueda: (String)
-
* @param key: (String). Corresponde a la clave en la que buscar si se trata de un array asociativo
-
* @return Devuelve -1 si no se ha encontado la coincidencia o, si se ha encontrado, la posición
-
* en el Array donde se encuentra (la de índice menor en el caso que esté repetida)
-
*/
-
static public function binarySubstringSearch ( arrayDeBusqueda:Array, terminoBusqueda:String, key:String ):Number
-
{
-
var strLen:Number = terminoBusqueda.length;
-
var alto:Number = arrayDeBusqueda.length;
-
var medio:Number;
-
var bajo:Number = -1;
-
while ((alto - bajo)> 1)
-
{
-
medio = Math.floor ((alto + bajo) / 2);
-
if (key==undefined) var arrValue=arrayDeBusqueda[medio]; else var arrValue = arrayDeBusqueda[medio][key];
-
var substrDeBusqueda:String = arrValue.substr (0, strLen);
-
if (substrDeBusqueda <terminoBusqueda)
-
{
-
bajo = medio;
-
}
-
else
-
{
-
alto = medio;
-
}
-
}
-
if (key==undefined) var arrValue=arrayDeBusqueda[alto]; else var arrValue = arrayDeBusqueda[alto][key];
-
var substrDeBusqueda:String = arrValue.substr (0, strLen);
-
if (alto == arrayDeBusqueda.length or substrDeBusqueda != terminoBusqueda)
-
{
-
return -1;
-
}
-
else
-
{
-
return alto;
-
}
-
}
-
}
