linear or binary search

JavaScript performance comparison

Revision 3 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

var n = 70 // The size of the arrays
// initialize an array with n sorted from smallest to largest
var a = new Uint8Array(n)
var i = n
while (i--)
  a[i] = i

function linearsearch(a, x) {
  var k = n
  while (k--)
    if (x > a[k]) break
  return k

function binarysearch(a, x) {
  var start = 0, end = n
  while (start !== end) {
    var mid = (start + end) >>> 1 // convert to int
    if (x > a[mid]) start = mid + 1
    else end = mid
  return start
Benchmark.prototype.setup = function() {
    var x = Math.random() * n

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