linear or binary search

JavaScript performance comparison

Revision 2 of this test case created


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

Benchmark.prototype.setup = function() {
    var n = 75  // The size of the arrays
    var x = n*Math.random()
    // 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 = Math.floor((start + end) / 2);
            if (x > a[mid]) {
              end = mid;
            else {
              start = mid + 1;
          return start;

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, x)
binary search
binarysearch(a, x)

Compare results of other browsers


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:


Comment form temporarily disabled.

Add a comment