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);
          return binarySearch(array, value, middle + 1,

Here’s how to use it:

binarySearch(arrayOfStrings, "myArrayItem", 0,

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

Tags: , , , , ,

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();
    //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.

Join the discussion