linear or binary search
JavaScript performance comparison
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>
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
}
</script>
<script>
Benchmark.prototype.setup = function() {
var x = Math.random() * n
};
</script>
Test runner
Warning! For accurate results, please disable Firebug before running the tests. (Why?)
Java applet disabled.
Test  Ops/sec  

linear search 

pending… 
binary search 

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:
 Revision 1: published by David Flanagan
 Revision 2: published
 Revision 3: published
 Revision 6: published
 Revision 7: published
0 comments