AS3: Main
Intro
|Link to article on Wikipedia|
When you're working with large array's, you often have to search for specific elements. Speed can become an issue if your array's length is in the thousands and it will quickly bog down performance. Binary searches allow you to drastically increase the speed by which you find the information you're looking for. In my testing I found this to be about twice as fast as a Array.indexOf() for very large arrays.
How It Works
Binary searches start with the array's middle element, then, depending on whether the search term is higher or lower than that term, it will move to the appropriate place in the array (higher or lower). You can immediately see why the array MUST BE SORTED for this method to work, otherwise it will likely not find the term.
The Code
function bsearch(array:Array,searchValue:*,sortOption:uint = 16):*
{
var tempArray:Array = array; //use a temporary array for sorting
if (sortOption != 0) //a sort option of 0 will assume the array is already sorted
tempArray = tempArray.sort(sortOption); //else it will sort by the given sort option (explained below)
var b:int = 0;//bottom search index
var t:int = tempArray.length-1;//top search index
while (b <= t)//as long as the indexes have not crossed
{
var index:uint = (b+t)/2//search the middle of the indexes
if (tempArray[index] == searchValue)//have you found the value?
{
if (sortOption != 0)//the value was found! If the array was presorted it will return the index, otherwise it will just return true
return true;
else
return index;
}
else if (tempArray[index] < searchValue)//if the value checked is lower than the search term, it will check the higher portion
{
b = index+1;
}
else//otherwise it will check the lower portion
{
t = index-1;
}
}
if (sortOption != 0)//if the item is never found it will return false or -1 (depending on whether or not the array was already sorted
return false;
else
return -1;
}
For the sortOption use one of the Array sort options, or 0, if you've already sorted it.
Cons
This search method will not find all instances of the term, nor will it return the first or last instance. It will only return the first instance it finds. Also the speed increase will vary greatly depending on where the variable is located.
Conclusion
Thanks for reading, if you have any questions or comments, feel free to post below!
