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.
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;
}