TechFindings

Arrays are simple datastructures but finding elements is not fast. However, if you have a sorted array, a favourite algorithm is Binary Search.

When it comes to JavaScript there is no binary search in the standard library. Standard functions like find and indexOf simply just don’t cut it for many purposes, being O(n).

Rosetta Code has two implementations of binary search for JavaScript. However, binary search is based on division (by 2, you split the search interval in half every iteration). In programming languages with integer math division by 2 is performed by doing a single shift, so it is a cheap operation (division is generally expensive). In JavaScript integer division by two looks like:

mid = Math.floor((lo + hi) / 2);

This is just… unacceptable. Perhaps V8 recognizes the pattern and replaces it with the right thing, I don’t care, floating point math has nothing to do with binary search and this is ugly.

Perhaps I can do better? Well, I actually can!

Instead of dividing the actual interval by 2 in every iteration you can use the powers of two: 32,16,8,4,2,1 and search with them. Lets say the array is 41 elements long. Start check element 32. If its too little try with 32+8 (skip 32+16 > 41), and if it is too large try with 16. That way you essentially do a binary search without a division.

Since I don’t want to do heap allocation for every search I calculate the powers of two before declaring the function. In the code below my maximum value is 2^31, so I can mostly search arrays of size 2^32-1. If you dont like that limit you can raise 32 to whatever you like (but at 52-53 you are running into new problems, and well before that you will run out of RAM).

function powers_init(s) {
  var i;
  var r = new Array(s);
  r[0] = 1;
  for ( i=1 ; i<s ; i++ ) {
    r[i] = 2*r[i-1];
  }
  return r;
}

var powers = powers_init(32);  // [1,2,4,8,16,32,...

function binary_search_divisionless(a, value) {
  var pix = 0;
  var aval;
  var offset0 = 0;
  var offset1;

  if ( a[0] === value ) return 0;
  while ( powers[pix+1] < a.length ) pix+= 1;

  while ( 0 <= pix ) {
    offset1 = offset0 + powers[pix];
    if ( offset1 < a.length ) {
      aval = a[offset1];
      if ( value === aval ) {
        return offset1;
      } else if ( aval < value ) {
        offset0 = offset1;
      }
    }
    pix--;
  }

  return -1;
}

It is perhaps not obvious why I check for a[0] before doing anything else. The function returns from the main while loop as soon as it finds what it is looking for. So a[offset0] does not contain the value in later iterations when offset>0. However, this is not guaranteed from the beginning when offset0=0, and it is not automatically being tested in the end. So I explicitly test it first.

Benchmark
Below follows relative performance in time for different array sizes.

Array Size:                  10      100     1000    10000   100000
=======================================================================
Standard Library indexOf   1.65     2.02    11.89    94.00   790.00
Rosetta Code Recursive     1.32     1.48     1.84     1.81     2.02
Rosetta Code Imperative    1.18     1.08     1.41     1.43     1.45
Divisionless               1.00     1.00     1.00     1.00     1.00
   - unrolled              0.93     0.76     0.82     0.79     0.78

I am satisfied that my code is consistently faster than the alternatives. What surprised me was that binary search clearly wins even for short arrays (10). The little loop before the big loop can be unrolled for significant performance gain:

//while ( powers[pix+ 1] < a.length ) pix+= 1;
  if ( powers[pix+16] < a.length ) pix+=16;
  if ( powers[pix+ 8] < a.length ) pix+= 8;
  if ( powers[pix+ 4] < a.length ) pix+= 4;
  if ( powers[pix+ 2] < a.length ) pix+= 2;
  if ( powers[pix+ 1] < a.length ) pix+= 1;

This is also the reason why 32 was a particularly good array size for the powers of two. This is a kind of optimization I would normally not let into my code. However, if you make much use of binary search on the Node.js server side of an application, go ahead.

It is also worth noting that the following patch doubles the execution time of my code!

//  if ( offset1 < a.length ) {
//    aval = a[offset1];
    if ( undefined !== ( aval = a[offset1] ) ) {

General Compare Function
With little modification, the algorithm can be used with a compare function for arrays of objects other than numbers (or strings).

Division
Since my algorithm only uses powers of 2, I can do division in JavaScript without using Math.floor. It is a quite easy change to eleminate the powers-array and divide by two instead. It turns out it make very little difference on performance (to do integer / 2 instead of array lookup). However, when I added a (meaningless) Math.floor() around the division, performance dropped the same as the the iterative version from Rosetta Code. So my intuition was correct to avoid it.

I checked the Lodash binary search code (sortedIndexOf) and it uses bit shift >>> to divide by two. Admittedly, the Lodash code is slightly faster than my code.

Conclusion
You should have a well implemented and tested binary search function available in your toolbox (admittedly, use Lodash for this). This is not the right place to lose milliseconds. For very small arrays you can argue that indexOf works equally well, but the cost of using binary search is insignificant.