Linear vs Binary Search

Benchmark created on

Setup

let LEN = 32
let a = []
for (let i = 1; i <= LEN; i += 1) {
	a.push(i)
}
let random = 1 + Math.random()*LEN|0
let result = 0

Teardown

console.log(random, result)

Test runner

Ready to run.

Testing in
TestOps/sec
Native linear search
result = a.indexOf(random)
ready
Linear search
for (let i = 0; i < a.length; i += 1) {
	if (a[i] === random) {
		result = i
		break
	}
}
ready
Binary search
let min = 0, max = a.length - 1
while (true) {
	let i = (max-min)/2 + min|0
	if (a[i] === random) {
		result = i
		break
	}
	if (i === min) {
		if (a[max] === random) {
			result = max
		} else {
			throw "couldn't find it'"
		}
		break
	}
	if (random > a[i]) {
		min = i+1
	} else {
		max = i-1
	}
}
ready
Binary search (no short-circuit)
let min = 0, max = a.length - 1
while (true) {
	if (max <= min + 1) {
		if (a[min] === random) {
			result = min
		} else if (a[max] === random) {
			result = max
		} else {
			throw "couldn't find it'"
		}
		break
	}
	let i = (max-min)/2 + min|0
	if (random > a[i]) {
		min = i+1
	} else {
		max = i
	}
}
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.