Implement a Binary search function which return the search path
Using Math.floor for calculating index to get the right path
Try to implement in recursion / iteration
##Powered by CodeWarrior
Implement a Binary search function which return the search path
Using Math.floor for calculating index to get the right path
Try to implement in recursion / iteration
##Powered by CodeWarrior
module.exports = function(array, value) { | |
var left = 0; | |
var right = array.length - 1; | |
var tracker = []; | |
while (left <= right) { | |
var mid = Math.floor((left + right) / 2); | |
tracker.push(array[mid]); | |
if (array[mid] == value) return tracker ; | |
if (array[mid] < value) { | |
left = mid + 1; | |
} else { | |
right = mid - 1; | |
}; | |
} | |
return tracker; | |
} |
{ | |
"id": 1, | |
"name": "binary search", | |
"level": "basic", | |
"author": "Jimmy Chao" | |
} |
var expect = require('expect.js'); | |
var binarysearch = require('./'); | |
describe("binary search", function() { | |
var array = [1, 2, 3, 4, 5, 6]; | |
var array2 = [3, 6, 10, 12, 15, 20, 22, 25, 27, 29, 41, 45, 46, 58]; | |
it("should return search path", function() { | |
expect(binarysearch(array, 3)).to.eql([3]); | |
expect(binarysearch(array, 1)).to.eql([3, 1]); | |
expect(binarysearch(array, 5)).to.eql([3, 5]); | |
expect(binarysearch(array, 6)).to.eql([3, 5, 6]); | |
}); | |
it("should search elements", function() { | |
expect(binarysearch(array2, 29).pop()).to.equal(29); | |
expect(binarysearch(array2, 15).pop()).to.equal(15); | |
expect(binarysearch(array2, 7).pop()).to.not.equal(7); | |
}); | |
}); |