linear or binary search

JavaScript performance comparison

Test case created by David Flanagan

Info

For relatively short sorted arrays, it is faster to use linear or binary search to find the right point to insert a new value?

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var n = 70  // The size of the arrays
   
    // initialize an array with n sorted from largest to smallest
    var a = [];
    for(var i = 0; i < n; i++)
      a[i] = n-i;
   
    function linearsearch(a, x) {
      for(var i = 0; i < n; i++)
        if (x > a[i]) break;
      return i;
    }
   
    function binarysearch(a, x) {
          var start = 0, end = n;
          while (start !== end) {
            var mid = ((start + end) / 2) | 0; // convert to int
            if (x > a[mid]) {
              end = mid;
            }
            else {
              start = mid + 1;
            }
          }
          return start;
    }
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
linear search
linearsearch(a, n*Math.random())
pending…
binary search
binarysearch(a, n*Math.random())
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment