To lea javascript, I implement and test classic algorithms with it.
Here is my attempt at implementing binary search and tests for it:
var assert = require('assert')
function binsearch (xs, v) {
if (xs === undefined || xs.length === 0) { retu null }
var lo = 0
var hi = xs.length - 1
while (lo <= hi) {
var i = (lo + hi) / 2 | 0
if (xs[i] === v) {
retu i
} else if (v < xs[i]) {
hi = i - 1
} else if (v > xs[i]) {
lo = i + 1
}
}
retu null
}
var check_bsearch = function (bsearch, xs, x, i) {
it(bsearch.name + ' [' + xs + '] ' + x + ' ' + i, function () {
assert.equal(bsearch(xs, x), i)
})
}
describe('Test binsearch', function () {
describe('on a sorted array', function() {
var xs = []
for (var i = 0; i < 2; ++i) {
xs[i] = 2 * i
for (var j = 0; j <= i; ++j) {
check_bsearch(binsearch, xs, 2 * j, j)
check_bsearch(binsearch, xs, 2 * j + 1, null)
check_bsearch(binsearch, xs, -1, null)
check_bsearch(binsearch, xs, -2, null)
check_bsearch(binsearch, xs, 2 * i + 1, null)
check_bsearch(binsearch, xs, 2 * i + 2, null)
}
}
})
})
In order to reproduce what I am about to say, copy the code above into some bsearch.js file, install mocha.js with something like sudo npm install -g mocha and finally run the file: mocha bsearch.js
One test should be failing: the one with xs = [0], x = 2 and expected result of null. If you recreate this test separately though, it will pass.
I am suspecting that this is a closure issue. You might have noticed that I am already using a helper function check_bsearch to get the expected closure environment. However, I am clearly missing something. How do I fix the tests?
