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

AS3 Binary Search

October 13, 2009Danwize 4 Comments »

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.

Tags: , , , , ,

This entry was posted on Tuesday, October 13th, 2009 at 11:04 am and is filed under Actionscript in Flash/Flex. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

4 Responses to this entry

  • xalaseta Says:
    Posted on April 11th, 2010 at 12:04 pm

    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:
    Posted on April 21st, 2011 at 12:46 pm

    What on earth is “myArrayForIndexes.length”?

  • bob Says:
    Posted on June 29th, 2011 at 2:36 pm

    what is “myArrayForIndexes”?

  • Danwize Says:
    Posted on July 6th, 2011 at 4:58 pm

    @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.

Join the discussion