nano-binary-search NPM version

A tiny, single-file binary search with no dependencies — plus the familiar sorted-array operations built on it: indexOf(), includes(), insert(), remove(), and friends. TypeScript typings are included.

After writing it countless times, I believe this version is done right and fits JavaScript — a perfect companion for sorted arrays.

What "done right" means here: every result is a valid Array.prototype.splice() index, unconditionally. Empty arrays, out-of-range values, duplicates, sub-ranges — all return an index you can pass straight to splice() without any check, and the array stays sorted afterwards. No ifs or buts.

This is equivalent to C++ std::lower_bound / Python bisect.bisect_left.

npm install nano-binary-search

import binarySearch from 'nano-binary-search';
// Lower bound (first element >= value):
binarySearch([1, 2, 4, 5], x => x < 3); // → 2
// Upper bound (first element > value):
binarySearch([1, 2, 4, 5], x => x <= 2); // → 2
// Insert keeping sorted order:
const idx = binarySearch(sortedArray, x => x < value);
sortedArray.splice(idx, 0, value);
// Remove all elements equal to value:
const lo = binarySearch(sortedArray, x => x < value);
const hi = binarySearch(sortedArray, x => x <= value, lo);
sortedArray.splice(lo, hi - lo);
// Edge cases — just work:
binarySearch([], x => x < 5); // → 0 (empty array)
binarySearch([1, 2, 3], x => x < 1); // → 0 (before all)
binarySearch([1, 2, 3], x => x < 4); // → 3 (after all)

The same operations — and more — are available as ready-made functions:

import {indexOf, lastIndexOf, includes, count, insert, remove, removeAll} from 'nano-binary-search';
const a = [1, 3, 3, 5];
indexOf(a, 3); // → 1 (first of the run)
lastIndexOf(a, 3); // → 2
includes(a, 4); // → false
count(a, 3); // → 2
insert(a, 4); // → 3; a is now [1, 3, 3, 4, 5]
remove(a, 4); // → true; a is now [1, 3, 3, 5]
removeAll(a, 3); // → 2; a is now [1, 5]

Why do I think it is done right? Because it supports important invariants with splice().

import binarySearch from 'nano-binary-search';
const sortedArray = [];
for (let i = 0; i < 100; ++i) {
 const value = Math.floor(Math.random() * 1000);
 // THIS IS THE IMPORTANT INVARIANT:
 // - works with `splice()` seamlessly to add values
 const index = binarySearch(sortedArray, x => x < value);
 sortedArray.splice(index, 0, value);
 // `sortedArray` is always sorted
}

What if the array is empty? That's fine. What if the value is outside the range of the array? That's fine too.

This idiom ships ready-made as insert(sortedArray, value).

import binarySearch from 'nano-binary-search';
const sortedArray = [1, 3, 3, 4];
// THIS IS THE IMPORTANT INVARIANT:
// - works with `splice()` seamlessly to remove equal values
const lowerIndex = binarySearch(sortedArray, x => x < 3),
 upperIndex = binarySearch(sortedArray, x => x <= 3, lowerIndex);
sortedArray.splice(lowerIndex, upperIndex - lowerIndex);
// again, `sortedArray` is always sorted

What if there is no such value in the array? That's fine. It still works.

Packaged as removeAll(sortedArray, value); remove() drops just the first match.

There is no need to pass in a function and a comparison value every time. In modern JavaScript/TypeScript it is easier to capture the comparison value in a closure, as shown in the examples above.

Do you want to search a sub-array? Just pass in indices.

TypeScript-like API:

const index: number = binarySearch<T>(
 sortedArray: readonly T[],
 lessFn: (value: T, index: number, array: readonly T[]) => boolean,
 l: number = 0,
 r: number = sortedArray.length
): number;

• Inputs:
  • sortedArray — sorted array of values. The array must be sorted in a way compatible with lessFn.
  • lessFn — function that takes three arguments and returns true if the element (first argument) is less than the target value. The second argument is the index, the third is sortedArray. The signature mirrors the standard array callback convention.
  • l — left index. This index is inclusive. Defaults to 0.
  • r — right index. This index is exclusive. Defaults to sortedArray.length.

The function returns an index where the target value can be inserted with splice():

• With <: the index of the first element greater than or equal to the target (lower bound, C++ std::lower_bound / Python bisect_left).
• With <=: the index of the first element greater than the target (upper bound, C++ std::upper_bound / Python bisect_right).

All of them are thin wrappers around binarySearch(). Instead of a closure they take the value directly plus an optional binary predicate less(a, b), which defaults to (a, b) => a < b. The array must be sorted compatibly with less, and the value must be comparable under it. Where equality is needed, it is derived from the ordering — two values are equal when neither is less than the other — and costs a single extra less() call after the search.

Queries (l/r are optional sub-range bounds, as in binarySearch()):

• lowerBound(sortedArray, value, less?, l?, r?) — the index of the first element ≥ value.
• upperBound(sortedArray, value, less?, l?, r?) — the index of the first element > value.
• indexOf(sortedArray, value, less?, l?, r?) — the index of the first equal element, or -1.
• lastIndexOf(sortedArray, value, less?, l?, r?) — the index of the last equal element, or -1.
• includes(sortedArray, value, less?, l?, r?) — whether an equal element is present.
• equalRange(sortedArray, value, less?, l?, r?) — the [lo, hi) span of equal elements; splice(lo, hi - lo) removes them all.
• count(sortedArray, value, less?, l?, r?) — the number of equal elements.

Mutators:

• insert(sortedArray, value, less?) — inserts keeping the sort order, after any equal elements (like Python's bisect.insort); returns the insertion index.
• remove(sortedArray, value, less?) — removes the first equal element; returns true if something was removed.
• removeAll(sortedArray, value, less?) — removes all equal elements; returns their number.

That's all Folks!

Is it fast?

Yes.

The only way to make it meaningfully faster is to inline the entire search in your code, eliminating the function-call overhead of lessFn().

What if I want to take into account the index of the searched value?

That's why lessFn(value, index, array) has extra arguments.

What if the array uses a custom comparator for sorting, while this binary search uses a less function?

Either convert it inline:

let compareFn; // some complex function defined elsewhere
sortedArray.sort(compareFn);
let value; // some search value defined elsewhere
const lessFn = x => compareFn(x, value) < 0,
 index = binarySearch(sortedArray, lessFn);

— or derive it with meta-toolkit's comparator adapters, so sort and search stay in sync from a single source. The derived predicate plugs straight into every value-based function:

import {lessFromCompare} from 'meta-toolkit/comparators';
const less = lessFromCompare(compareFn); // (a, b) => boolean, built once
sortedArray.sort(compareFn);
const index = indexOf(sortedArray, value, less);

The adapter approach pays off when one comparator drives multiple searches, when you need the inverse direction (compareFromLess — e.g., you started with a less function and need a sort() comparator), descending order (reverseLess / reverseCompare), or derived equality (equalFromLess). All five adapters live in meta-toolkit/comparators.

Why doesn't it use a comparator function for searching?

Binary search does not need equality comparison — a simple less function is sufficient and often easier to implement.

For example (two argument version for simplicity):

const stringLessFn = (a, b) => a < b;
// comparator #1 (two comparisons)
const stringCompareFn1 = (a, b) => (a < b ? -1 : a > b ? 1 : 0);
// comparator #2: smarter (a method call)
const stringCompareFn2 = (a, b) => a.localeCompare(b);

I still have questions!

Look at the code of index.js and tests/ for more details. Go to the GitHub repository and ask.

The package ships its machine-checkable claims as data: INVARIANTS.md — preconditions, postconditions, cross-function laws, mutator effects, replacement patterns with their call-site obligations, and hazards, with executable checks embedded as fenced code blocks. The test suite (tests/test-invariants.js) compiles those checks and holds the implementation to them with property tests, so the claims are verified, never trusted. The file is included in the npm tarball: tools and agents can read the contract straight from node_modules.

To find the file, read the invariants field in package.json, which points at it the way types points at the declarations; the root filename is a fallback. The frontmatter states what the claims cover: sidecar is the format version, package matches this package's name, binds is the version range the claims describe, and verified: ci marks them as checked by continuous integration rather than advisory. The invariants-sidecar package parses the format and compiles the executable checks.

This project is licensed under the BSD-3-Clause license.

• 1.2.0 Ships INVARIANTS.md, the machine-checkable contract with executable checks, discoverable via the new invariants field in package.json
• 1.1.0 Added sorted-array functions built on the binary search: indexOf, includes, insert, remove, and friends
• 1.0.14 Minor housekeeping. Updated dev deps
• 1.0.13 Updated dev deps
• 1.0.12 Exported LessFn type, added TS typing tests and CJS tests, improved docs and d.ts JSDoc
• 1.0.11 Technical release: more tests to increase coverage, more AI-friendly changes
• 1.0.10 Updated dev deps
• 1.0.9 Updated dev deps
• 1.0.8 Updated dev deps
• 1.0.7 Updated dev deps
• 1.0.6 Updated dev deps
• 1.0.5 Updated dev deps
• 1.0.4 Updated dev deps
• 1.0.3 Added a reference to the TS types
• 1.0.2 Improved docs
• 1.0.1 Added TS typings
• 1.0.0 Initial release