Package Exports
- binary-search-insert
This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (binary-search-insert) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.
Readme
binary-search-insert
A library for performing a binary search and insert into a sorted array.
Binary search has an average time complexity of O(log(n)) which is substantially faster than a linear search
with an average time complexity of O(n).
Installing
$ npm install binary-search-insertUsage
var binarySearchInsert = require('binary-search-insert');
var sortedArray = [1, 3, 5, 7, 9, 11];
var comparator = function (a, b) { return a - b; }
/**
* Mutates sortedArray and returns index of inserted value
* @param {Array} A sorted array
* @param {*} An item to insert in the sorted array
* @param {Function} A comparator function that takes two arguments and returns a number. The first
* argument will be a member of sortedArray, the second argument will be item.
* If item < member, return value < 0
* If item > member, return value > 0
* @returns {Number} index of array where item is inserted
*/
var indexInsertedAt = binarySearchInsert(sortedArray, comparator, 6);
// indexInsertedAt: 3
// sortedArray: [1, 3, 5, 6, 7, 9, 11]Benchmarks
http://jsperf.com/cflynn07-binary-search-insert-vs-linear-search-insert
Testing
// Tests + coverage reports are run using Lab
$ npm test
// Test coverage reports
$ npm run test-cov # will auto-open Google Chrome with html coverage report