binary-search-bounds

What is binary-search-bounds?

The binary-search-bounds npm package provides utilities for performing binary search operations on sorted arrays. It allows you to find the insertion points for elements, as well as the lower and upper bounds for elements in a sorted array.

What are binary-search-bounds's main functionalities?

binarySearch

This feature allows you to perform a binary search to find the exact index of an element in a sorted array. In this example, the element 3 is found at index 2.

const bsb = require('binary-search-bounds');
const arr = [1, 2, 3, 4, 5];
const index = bsb.eq(arr, 3); // 2
console.log(index);

lowerBound

This feature allows you to find the lower bound (first occurrence) of an element in a sorted array. In this example, the first occurrence of the element 2 is at index 1.

const bsb = require('binary-search-bounds');
const arr = [1, 2, 2, 2, 3, 4, 5];
const index = bsb.ge(arr, 2); // 1
console.log(index);

upperBound

This feature allows you to find the upper bound (first element greater than the given element) in a sorted array. In this example, the first element greater than 2 is at index 4.

const bsb = require('binary-search-bounds');
const arr = [1, 2, 2, 2, 3, 4, 5];
const index = bsb.gt(arr, 2); // 4
console.log(index);

insertionPoint

This feature allows you to find the insertion point for an element in a sorted array. In this example, the insertion point for the element 3 is at index 2.

const bsb = require('binary-search-bounds');
const arr = [1, 2, 3, 4, 5];
const index = bsb.le(arr, 3); // 2
console.log(index);

Other packages similar to binary-search-bounds

binary-search

The binary-search package provides basic binary search functionality for sorted arrays. It is simpler and less feature-rich compared to binary-search-bounds, focusing mainly on finding the index of an element.

lodash

Lodash is a utility library that provides a wide range of functions, including binary search methods like _.sortedIndex and _.sortedLastIndex. While it offers more general-purpose utilities, its binary search functionalities are comparable to those in binary-search-bounds.

bsearch

The bsearch package offers binary search utilities for sorted arrays, similar to binary-search-bounds. It provides methods for finding exact matches, lower bounds, and upper bounds, making it a close alternative.

README

binary-search-bounds

Binary search on arrays for predecessor, successor and range queries.

Rationale

The main reason for using a binary search or ordered set data structure instead of a hash map is to support fast predecessor/successor queries. Besides this library, I am aware of no other modules on npm which implement these semantics (making them effectively useless)!!! binary-search-bounds corrects this sad state of affairs.

Example

//Import module
var bounds = require('binary-search-bounds')

//Create an array
var array = [1, 2, 3, 3, 3, 5, 6, 10, 11, 13, 50, 1000, 2200]

//Print all elements in array contained in the interval [3, 50)
console.log(
  array.slice(
    bounds.ge(array, 3),
    bounds.lt(array, 50)))

//Test if array contains the element 4
console.log('indexOf(6)=', bounds.eq(array, 6))
console.log('indexOf(4)=', bounds.eq(array, 4))

//Find the element immediately after 13
console.log('successor of 13 = ', array[bounds.gt(array, 13)])

//Find the element in the array before 4
console.log('predecessor of 4 = ', array[bounds.lt(array, 4)])

//Create an array of objects
var creatures = [
  { legs: 8, name: 'spider' },
  { legs: 4, name: 'mouse' },
  { legs: 4, name: 'cat' },
  { legs: 2, name: 'Ben Franklin' },
  { legs: 4, name: 'table', isCreature: false },
  { legs: 100, name: 'centipede' },
  { legs: 4, name: 'dog' },
  { legs: 6, name: 'ant' }
]

//Sort the array by number of legs
function byLegs(a,b) { return a.legs - b.legs }
creatures.sort(byLegs)

//Find the next creature with more than 4 legs
console.log('What has more than 4 legs? Answer: ', creatures[bounds.gt(creatures, {legs:4}, byLegs)])

Output:

[ 3, 3, 3, 5, 6, 10, 11 ]
indexOf(6)= 6
indexOf(4)= -1
successor of 13 = 50
predecessor of 4 = 3
What has more than 4 legs? Answer: { legs: 6, name: 'ant' }

Install

Using npm, you can install the library as follows:

npm install binary-search-bounds

This module works great with browserify if you want to use it in front end projects.

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. This is the same as a predecessor query.

bounds.le(array, y[, cmp, lo, hi])

Returns the index of the last item in the array <= y. This is a predecessor query which also returns the item if present.

bounds.gt(array, y[, cmp, lo, hi])

Returns the index of the first item in the array > y. This is the same as a successor query.

bounds.ge(array, y[, cmp, lo, hi])

Returns the index of the first item in the array >= y. This is a successor query which also returns the item if present.

bounds.eq(array, y[, cmp, lo, hi])

Returns an index of some item in the array == y or -1 if the item is not present.

Notes

The following comments apply to the above methods:

• cmp is a comparison function, just like what you would pass to Array.sort()
• y will always be the second argument passed to cmp, 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 search. If not specified defaults to 0.
• hi gives an upper bound on the array index to search. If not specified defaults to array.length-1
• The range [lo,hi] is inclusive (closed)
• bounds.le and bounds.lt will return lo - 1 if no element is found that ==y
• bounds.ge and bounds.gt will return hi + 1 if no element is found that ==y
• bounds.eq will return -1 if no element matching y is found.
• bounds.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 and do not care where it is.

Credits

(c) 2013-2015 Mikola Lysenko. MIT License