Algorithms: Javascript Array indexOf vs Binary Search vs Hash Access

I’ve been getting into algorithms lately, and I wanted to try out adding binary search to Simply Is, a simple type testing javascript utility I wrote a while back. But, surprisingly, it ended up being slower than the native Javascript array indexOf. Less surprisingly though, hash access was the fastest. Actually, creating a hash from the array then accessing it was actually still faster than the binary search (though slower than the native array indexOf).

My theory is that this result probably has to do with how Javascript works under the hood. Something worth looking into would be how Array indexOf is implemented in the Javascript source. It might be possible that since it’s built-in/operating at a lower level, there’s less overhead and thus performs better.


Binary search – 216,774 ops/sec

function binary_search(x,arr){
    if( typeof arr[0] === 'number' ){
        arr = arr.sort(function(x,y){ return Number(x) - Number(y) })
    }else{
        arr = arr.sort()
    }

    var min = 0,
        max = arr.length - 1,
        current_guess = Math.floor( (min + max)/2 )
        
    var found = false

    if( x === arr[current_guess] ){
        found = true
    }else if( x < arr[current_guess] ){ found = binary_search(x, arr.slice(min, current_guess) ) }else if( x > arr[current_guess] ){
        found = binary_search(x, arr.slice(current_guess + 1, max + 1))
    }

    return found
}

Array indexOf = 43,314,557 ops/second

var TEST_ARRAY = [2, 3, 17, 18, 22, 74, 25, 93, 43, 47, 48, 56, 59, 61, 64, 52, 71, 73, 75,37, 76, 77, 88, 21]
TEST_ARRAY.indexOf(73) > 0

Creating a hash from the array then accessing it = 809,269 ops/sec

   var TEST_HASH = {}
    TEST_ARRAY.forEach(function(value){
        TEST_HASH[value] = true
    })
    TEST_HASH[73]

(Existing) hash access = 90,671,807 ops/sec

TEST_HASH[73]

Either way, this result was somewhat surprising to me, since in terms of algorithms, binary search is supposed to be very fast. Then again, the comparison might not be completely fair, since the binary search is implemented at a higher level while the Array indexOf method is built-in. I wonder, though, how will it hold up if the array is very,very large? It’s possible that this result is only the case because the array that’s being searched is pretty small? Or, perhaps it has to do with the way I did the binary search (recursive calls on smaller array slices)? Maybe having to slice/create a new array is slowing it down?

Lots of possibilities for what may have led to this result. I’ll have to look into this a bit more one of these days.