linear or binary search

JavaScript performance comparison

Revision 6 of this test case created

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 < a.length; i++)
        if (x > a[i]) break;
      return i;
    }
   
    function binarysearch(a, x) {
          var start = 0, end = a.length-1;
          while (start !== end) {
            var mid = (start + end) >>> 1; // /2,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