Parable of the Laborers in the Vineyard Get Rid of Yellow Focus Rect

## AS3 Binary Search

Here is a simple recursive binary search function written in AS3.  This is a quick and efficient way to search an array.  In the worst case, binary search will take log2(n) steps to finish the search where n is the length of the array.  Of course this algorithm only works if the array has been sorted.  It returns the index of the item you search for.

``````
protected function binarySearch(array:Array, value:String,
left:int, right:int):int

{
if(left > right)
return -1;
var middle:int = (left + right) / 2;
if(array[middle] == value)
return middle;
else if(array[middle] > value)
return binarySearch(array, value, left,
middle - 1);
else
return binarySearch(array, value, middle + 1,
right);
}``````

Here’s how to use it:

``````binarySearch(arrayOfStrings, "myArrayItem", 0,
arrayOfStrings.length);``````

You’ll get back the array index of the item you were searching for. If it is not found, the function returns -1.

### 4 Responses to this entry

• xalaseta Says:

thanks y help me …
search strings that start with ’s’ this is very very faster from array filter … very very

public function likeSearch(s:String,dictArray:Array=null):Array
{
if(s.length==0)return new Array();
if(!dictArray)dictArray=story;
//return dictArray.filter(function (element:*, index:int, arr:Array):Boolean{if(String(element).substr(0,s.length)==s)return true;return false})
var i:int=binarySearch(dictArray,s,0,dictArray.length)
if(i==-1)return new Array();
var start:int;
var end:int;

for (var ii:int=i;ii>=0;ii–){
if(String(dictArray[ii]).substr(0,s.length) == s)start=ii; else ii=-1;
}
for (var iii:int=i;iii right) return -1;
var middle:int = (left + right) / 2;
if(String(array[middle]).substr(0,value.length) == value)return middle;
else if(array[middle] > value)return binarySearch(array, value, left,middle – 1);
else return binarySearch(array, value, middle + 1,right);
}

• bob Says:

What on earth is “myArrayForIndexes.length”?

• bob Says:

what is “myArrayForIndexes”?

• Danwize Says:

@Bob Sorry for taking so long to respond! I’ve been very bad at maintaining this blog lately. I fixed the post above, myArrayForIndexes was just a copy and paste error. You should see it now says arrayOfStrings. Make sure you sort the array before using binary search.