Wednesday, November 26, 2014

Binary Search vs. array.indexOf()

So I needed a binary search and decided to write a short tutorial on it. This binary search class uses ds.oop a small oop javascript framework which can be downloaded or cloned from github.

    ds.make.class({
        type: 'ArrayUtils.BinarySearch',
        constructor: function() {
        }
    });
Ok so this class is going to do a binary search of an array for us. If you don't know what a binary search is its just a much faster way of searching than simply starting at the beginning of a list and running through a for loop and testing each element to see if it matches. Instead of binary search starts in the middle and depending of if the value is more or less it jumps to the middle of the first half or the last half of the list. It continues to do this until it finds the matching item or until it can no longer divide up the list.
Visual representation of a binary decision tree.
So we know we need an array to search through so lets add an array property and initialize it with the constructor.

    ds.make.class({
        type: 'ArrayUtils.BinarySearch',
        properties: {
            array: []
        },
        constructor: function (array) {
            array.sort();
            this.array = array;
        }
    });

Ok great. Now we can pass in an array through the constructor and it will live in our class instance. Also we have sorted the array so the elements should be in alpha-numeric order. Now in order to do the binary search we will need to do some string comparisons so lets make a static class for all the string functions we will write.

    ds.make.static.class({
        type: 'string',
        compare: function (a, b) {
            if (a.toString() < b.toString()) return -1;
            if (a.toString() > b.toString()) return 1;
            return 0;
        }
    });

So now we can call `string.compare(a,b)` from anywhere and get a result. I could have just included this in the BinarySearch class, but we may want to use it again somewhere else in our project so its better if its in a separate class for string utility functions.

Ok so now we just need to add the search method.

    search: function (search) {
        var array = this.array;
        var length = array.length;
        var index = Math.floor(array.length * 0.5);

        while (length > 1) {
            var cmp = string.compare(search, array[index]);
            if (cmp == 0) return index;
            length = Math.ceil(length * 0.5);
            var half = Math.ceil(length * 0.5);
            index = index + (half * cmp);
        }
    }

So first this creates some local variables. We need to use `this.array` to access array now since it is a public property of the class. The index we use to search starts in the middle of the array. Then in the while loop we do a comparison between the search and the item at the current index. The result will be -1,0, or 1 (less than, equal, or greater than respectively). Then if its a match we return the index otherwise the index jumps to the middle of the first half or second half of the list and repeats the process.

Finally, lets test out the class and see if it works.
    var a = new ArrayUtils.BinarySearch(['Orange', 'Kiwi', 'Lime', 'Apple', 'Grape', 'Banana']);
    var index = a.search('Lime');
    alert('index: ' + index + '   item: ' + a.array[index]);

Ok. It seems like its works. We create the class instance and pass an array into it. Then we call the search method to return the index. Lets do a better test and also see how the speed compares to array.indexOf().

    // now lets test it
    var a = new ArrayUtils.BinarySearch(array);

    // accuracy test
    for (var i = 0; i < array.length; i++) {
        var item = array[i];
        var index = array.indexOf(item);
        var bindex = a.search(item);
        if (array[index] != array[bindex]) 
            throw 'The binary search result was incorrect!  i: ' +i +'  item: '+item+'  index: '
            +index + '>' +array[index]+'  bindex: '+bindex +'>' +array[bindex];
    }

    // speed test
    var iterations = 1000000;
    var old_time = (new Date()).getTime();
    for (var i = 0; i < iterations; i++) {
        var item = array[Math.floor(Math.random() * array.length)];
        var index = array.indexOf(item);
    }
    var new_time = (new Date()).getTime();
    var seconds_passed_indexOf = (new_time - old_time)/1000;

    old_time = (new Date()).getTime();
    for (var i = 0; i < iterations; i++) {
        var item = array[Math.floor(Math.random() * array.length)];
        var index = a.search(item);
    }
    new_time = (new Date()).getTime();
    var seconds_passed_binary_search = (new_time - old_time)/1000;

    alert(iterations + ' iterations\nindexOf:\t\t' + seconds_passed_indexOf 
            + '\nbinary search:\t\t' + seconds_passed_binary_search)

And here are the results. I ran the test with an array of 7000 random strings. As you can see, our BinarySearch class is waaaaayyy faster.

    1000000 iterations
    indexOf:  15.387 seconds
    binary search: 0.207 seconds

To see this class in action check out the tutorial folder. Thanks for reading!

No comments:

Post a Comment