Showing 1 - 2 of 2 total. RSS Feed WordPress RSS Feed

Binary search

Binary search is a way of searching data inside a sorted list that can drastically reduce the time of the search operations.
In this example I'm searching for an integer because it's the most reliable data type in as. When comparing strings or complex objects some expedient should be taken to be sure that the comparison it's correct. The Comparable interface of Java could be a good solution.
To give insight about how fast is this method, to run 500 searchs in a list of 1000000 items the binarySearch took 2 to 5 milliseconds doing only 16-17 comparisons.
The regular indexOf method of the Array class took 450 milliseconds to perform the same task.
The bit operations (>>>) used to take the middle number (probe) also helped a bit, using a regular division (/2) increased the time to run the task to 4-9 milliseconds.
public function binarySearch(keys:Array, target:int):int
{
var high:int = keys.length;
var low:int = -1;

while (high - low > 1)
{
var probe:int = (low + high) >>> 1;
if (keys[probe] > target)
{
high = probe;
}
else
{
low = probe;
}
}

return (low == -1 || keys[low] !== target) ? -1 : low;
}

actionscript 3.0 and e4x: search strings inside an XML object

Find a defined string inside an XML object
// String to Find
var stringToFind:String = "Flash Media";

// XML Object
var myXML:XML =
<order>
<item id='101'>
<title>Technologies</title>
<desc>XML e4x rulez</desc>
</item>

<item id='102'>
<title>Adobe Products</title>
<desc>Flex, Flash, Air, FlashLite, Catalyst, Flash Media Server 2, ... </desc>
</item>


<item id='103'>
<title>Server Side Products</title>
<desc>Flash Media Server 3, Flash Collaborative Service, ColdFustion</desc>
</item>

</order>


// Loop over the XML items
for (var i:uint = 0; i < myXML.item.length(); i++) {

// Get the item description
var tempString:String = myXML.item[i].desc


/*
* Check if the defined word does exist in the description, displaying:
* - Node title
* - Node ID
* - XML node index (from 0 to N)
* - The searched word
*/
if (tempString.search(stringToFind) != -1) {
// This trace displays:
// ---> Adobe Products ( ID - 102 ) contains this word: 'Flash Media' (XML item index: 1 )
// ---> Server Side Products ( ID - 103 ) contains this word: 'Flash Media' (XML item index: 2 )
trace("--->", myXML.item[i].title, "( ID -", myXML.item[i].@id, ") contains this word: '" + stringToFind + "' (XML item index:", i, ")")
}


}

Showing 1 - 2 of 2 total. RSS Feed WordPress RSS Feed