Binary search, from java to Actionscript

Question

Hi
I am trying to convert the following java binary search routine to as3. I assume that 'compareTo' is a built in java method and that '>>>' s a type of bitwise operation.

Can anyone familiar with both actionscript 3 and Java help with this?

package binary;

public class Finder {

  public static int find( String[ ] keys, String target) {
    int high = keys.length;
    int low = -1;
    while (high - low>1) {
      int probe = (low + high)>>> 1;
      if (keys[probe].compareTo(target) > 0)
        high = probe;
      else
        low = probe;
    }

    if (low==-1 || keys[low].compareTo(target) !=0)
      return -1;
    else
      return low;
  }
}

Answer 1

I cannot help you with Actionscript, but compareTo is indeed a standard Java method. It will compare the object it is invoked on against its argument and return a negative value if the object is less than the argument, positive if it is greater, and 0 if it is equal. The >>> operator is a right-shift operator; you can replace >>> 1 with / 2 (division by 2). Using the shift operator is just needless obfuscation these days when compilers are smart enough to replace division by a constant with a shift if that is better. (Aside: read this if your arrays have more than 2³⁰ elements...)

Answer 2

You should use the built-in Flash features as much as possible. It makes your code easier to maintain and the resulting SWF will be faster and smaller. Check out the indexOf() method on Array.

Is this homework or do you have some other reason for using a hand-written search?

Edit: I should add that the built-in search is a linear search starting with the index you provide. If you have a large and already sorted array, the binary search may be faster. You'll have to experiment where the cross-over is--it could be as low as 10. If your array is not already sorted, the built-in linear search will beat the pants off the combined sort and binary search.

Second Edit: I was curious how large the array had to be for indexOf() to become slower so I ran a few tests. Searching an array of 50 items, indexOf() is faster for all items. Searching an array of 100,000 items, indexOf() is faster up to about 100, then the binary search dominates.

To find the 50,000th item out of 100,000 items, binary search takes 0.0078ms while indexOf() takes 3.382ms.

Here's the test code. I've never performance tested AS3 before, so watching elapsed time on a quiescent machine is the best I've got. (sprintf is the implementation posted on SO. It is just used to generate strings.)

    private static var myArray:Array;

    public static function setup():void {
        myArray = new Array();
        for (var i:int=0; i < 50; ++i) {
            myArray[i] = sprintf("s%06d", i);
        }
    }

    public static function timingTest():void {
        if (myArray == null) {
            setup();
        }

        var start:Number = getTimer();
        for (var j:int=0; j < 5000; ++j) {
            if (binarySearch(myArray, "s000049") != 49) {
                trace("oops!");
            }
        }
        trace("avg msecs per binarySearch " + (getTimer() - start)/j);

        start = getTimer();
        for (var k:int=0; k < 5000; ++k) {
            if (myArray.indexOf("s000049") != 49) {
                trace("oops!");
            }
        }
        trace("avg msecs per indexOf " + (getTimer() - start)/k);
    }

    public static function binarySearch(keys:Array, target:String):int {
        var high:int = keys.length;
        var low:int = -1;
        while (high - low > 1) {
            var probe:int = (low + high) / 2;
            if (keys[probe] > target)
                high = probe;
            else
                low = probe;
        }
        if (low == -1 || keys[low] !== target)
            return -1;
        else
            return low;
    }
}

Answer 3

Here's a functional AS3 version:

    public static function find(keys:Array, target:String):int {
        var high:int = keys.length;
        var low:int = -1;
        while (high - low > 1) {
            var probe:int = (low + high) / 2;
            if (keys[probe] > target)
                high = probe;
            else
                low = probe;
        }

        if (low == -1 || keys[low] !== target)
            return -1;
        else
            return low;
    }

BTW, I would recommend you rename the function to be more meaningful, like binarySearch(), which indicates to the caller the array had better be sorted. A name like find() does not imply such.