binary-search-bounds
Better binary searching
npm install binary-search-bounds
Want to see pretty graphs? Log in now!
15 | downloads in the last week |
48 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.3.1 last updated 6 months ago |
License | MIT |
Keywords | binary, search, bounds, least, lower, greatest, upper |
Repository | git://github.com/mikolalysenko/binary-search-bounds.git (git) |
Bugs | https://github.com/mikolalysenko/binary-search-bounds/issues |
Dependencies | None |
Dependents (10) | 2-sat, aho-corasick-automaton, array-trie, bitmap-triangulate, dynamic-forest, game-shell, horn-sat, interval-tree-1d, mikolalysenko-hoarders, slab-decomposition |
Starred by | maxogden |
binary-search-bounds
Binary search on arrays. Also works if the inputs are 1D ndarrays.
API
var bounds = require("binary-search-bounds")
bounds.lt(array, y[, cmp, lo, hi])
Returns the index of the last item in the array <
y
bounds.le(array, y[, cmp, lo, hi])
Returns the index of the last item in the array <=
y
bounds.gt(array, y[, cmp, lo, hi])
Returns the index of the first item in the array >
y
bounds.ge(array, y[, cmp, lo, hi])
Returns the index of the first item in the array >=
y
bounds.eq(array, y[, cmp, lo, hi])
Returns an index of some item in the array == y
. -1
if not found.
Notes
array
can be either an array or anndarray
cmp
is a comparison function, just like what you would pass toArray.sort()
y
will always be the second argument passed tocmp
, so you can ignore it if you are just binary searching on a predicate- Assumes the array is sorted as would be the case if you called
Array.sort(cmp)
on it - If no comparison is passed, assume array is sorted in ascending order (note this is different than the semantics of Array.sort() which converts all entries to strings if you don't pass an argument)
lo
gives a lower bound on the array index to searchhi
gives an upper bound on the array index to searchbounds.le
andbounds.lt
will returnlo - 1
if no element is found satisfying the predicatebounds.ge
andbounds.gt
will returnhi + 1
if no element is found satisfying the predicatebounds.eq
will return the first found item with the given index. It can be a little faster than the other methods if you just want to find some random match.
Credits
(c) 2013 Mikola Lysenko. MIT License