JavaScript binary search

Question

I wrote an implementation of binary search in JavaScript earlier for kicks, but I noticed my version was significantly different than those found on Google. Here is an example of binary search I found on Google (copied here to combat link rot):

Array.prototype.binarySearch = function(find, comparator) {
    var low = 0, high = this.length - 1,
        i, comparison;

    while (low <= high) {
        i = Math.floor((low + high) / 2);
        comparison = comparator(this[i], find);
        if (comparison < 0) { low = i + 1; continue; };
        if (comparison > 0) { high = i - 1; continue; };
        return i;
    }
    return null;
};

Most of the other implementations on Google are quite similar. But in mine, I don't subtract one from the low/high and continue from there. Instead, I divide the array in half and continue dividing the appropriate side in half until I reach the proper value. Code:

function binary_search_iterative(arr, ele) {
    var beginning = 0, end = arr.length,
        target;
    while (true) {
        target = Math.floor((beginning + end) / 2);
        if ((target === end || target === beginning) && arr[target] !== ele) {
            return -1;
        }
        if (arr[target] > ele) {
            end = target;
        } else if (arr[target] < ele) {
            beginning = target;
        } else {
            return target;
        }
    }
}

I wrote this recursive-style as well, but in testing I found this iterative version was faster.

In my tests, I've found that the examples I've found on Google (though they did not include the one above, they were nearly identical) are faster on smaller arrays, but as the input size increases, mine overtakes those. Since binary searches are usually limited (?) to larger input sizes, I see this as an improvement.

Is my thinking correct? Could this be done in an even better way?

I also do not like this:

if ((target === end || target === beginning) && arr[target] !== ele) {
    return -1;
}

And I was curious if there is a good way to eliminate it or refactor the function where it's cleaner in general.

Answer 1

I would just like to hi-light a few points of difference in the two and how I think they are reflected in what you are seeing.

• When making a comparison between arr[target] and ele, if they are not the same then you do not need to include target within the bounds of the next iteration (hence the +/- 1). This can reduce the number of comparisons though the effect is more significant on smaller datasets.

• When following the above point, it becomes sufficient terminate as "not found" when beginning > end rather then check that you are looking at the beginning or end value. Also your approach may provide a false negative when looking for "B" in the following situation.

      target
      |
      v
  ... A B
      ^ ^
      | |
      | end
      beginning
  

  In this situation, because target === beginning and arr[target] !== B, it returns -1.

• The googled code uses parseInt, I'm not sure how this affects correctness but I suspect this has an adverse effect on the performance.

I think what you are seeing in the scalability is because the googled code does fewer comparisons but the parseInt makes the comparisons more expensive. The reduced number of comparisons is more significant for small data sets, but for larger data sets cost of the comparison becomes more significant.

I would suggest some experimentation/investigation to see if this is accurate.

Answer 2

Change Math.floor((beginning + end) / 2) to ((beginning + end) >> 1) means the same thing and is much quicker:

http://jsperf.com/code-review-1480

Answer 3

Honestly I've never been a fan of while(true). In my opinion its best to put your main conditional there for readability and style. Here is the version I wrote a while back for kicks, if it helps - my goal here was mostly fitting it in a tweet - but I beautified it for this example. Notice I am using Math.floor instead of parseInt - my tests indicated Math.floor was about twice as fast when there was a .5, and just a tiny bit faster when done on an integer. This version may look weird (the ternary upperbound is assigned to -2 when match found) but again it was a byte shaving experiment.

Array.prototype.binarysearch = function (o) {
     var l = 0, u = this.length,  m;
     while ( l <= u ) { 
         if ( o > this[( m = Math.floor((l+u)/2) )] ) l = m+1;
         else u = (o == this[m]) ? -2 : m - 1;
     }
     return (u == -2) ? m : -1;
}

Answer 4

Apart from the use of parseInt, the performance difference between the different approaches is likely to depend most on the Javascript implementation.

• With an aggressive optimizer (e.g. in a JIT compiler), the different versions will probably work out pretty much the same. For others, it will be a lottery.

• For any given Javascript platform it will be hard to predict which version of the code will perform best. If it really matters, (and I suspect it won't) you need to benchmark the different versions of method on all of the Javascript platforms that you care about.

Answer 5

Your code won't generate a false negative as suggested by Brian; 'end' always points at an element that is considered greater than the value to be found (treating past the array as a logical element).

Your code can reference the element past the end of the array, however. E.g. If the length of the array is zero, you will dereference arr[0]. In javascript, this might be acceptable, but for a C programmer, it looks weird.

The primary difference in performance is going to come from the fact that the googled code calls a subroutine to perform the comparison and your code performs the comparison in line. To properly compare the two approaches, you should race your code against the googled code with inlined comparisons.