# nano-binary-search

> Binary search (lower bound) for JavaScript and TypeScript, plus the familiar sorted-array operations built on it: `indexOf`, `includes`, `insert`, `remove`, and friends. Every result is an `Array.prototype.splice()`-compatible insertion index — no bounds checks needed. Zero dependencies, single-file ESM. Equivalent to C++ `std::lower_bound` / Python `bisect.bisect_left`.

- NPM: https://npmjs.org/package/nano-binary-search
- GitHub: https://github.com/uhop/nano-binary-search
- License: BSD-3-Clause
- Runtime: Node.js (every non-EOL release), Bun, Deno; no `engines` floor pinned
- Module system: ESM only (`"type": "module"`); CJS consumers use `require()` via Node's require-ESM interop (Node 22.12+)

## Installation

```bash
npm install nano-binary-search
```

## API

Module: `nano-binary-search` (root export only). `binarySearch` is exported both as default and by name; everything else is named-only.

```ts
export type LessFn<T = any> = (value: T, index: number, sortedArray: readonly T[]) => boolean;
export type Less<T = any> = (a: T, b: T) => boolean;

export declare function binarySearch<T>(sortedArray: readonly T[], lessFn: LessFn<T>, l?: number, r?: number): number;

export declare function lowerBound<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): number;
export declare function upperBound<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): number;
export declare function indexOf<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): number;
export declare function lastIndexOf<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): number;
export declare function includes<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): boolean;
export declare function equalRange<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): [lo: number, hi: number];
export declare function count<T>(sortedArray: readonly T[], value: T, less?: Less<T>, l?: number, r?: number): number;

export declare function insert<T>(sortedArray: T[], value: T, less?: Less<T>): number;
export declare function remove<T>(sortedArray: T[], value: T, less?: Less<T>): boolean;
export declare function removeAll<T>(sortedArray: T[], value: T, less?: Less<T>): number;

export default binarySearch;
```

### The core primitive: `binarySearch(sortedArray, lessFn, l?, r?)`

- `sortedArray` — array sorted in a way compatible with `lessFn`.
- `lessFn(value, index, sortedArray)` — returns `true` if `value` is less than the pivot. Follows the standard array-callback convention: the second argument is the index of `value`, the third is the array itself.
- `l` — left index, inclusive. Defaults to `0`.
- `r` — right index, exclusive. Defaults to `sortedArray.length`.

Semantics:

- With `<` in `lessFn`: returns the index of the first element ≥ pivot (**lower bound**, C++ `std::lower_bound` / Python `bisect_left`).
- With `<=` in `lessFn`: returns the index of the first element > pivot (**upper bound**, C++ `std::upper_bound` / Python `bisect_right`).

### Value-based functions

All are thin wrappers around `binarySearch`. Shared conventions:

- `less(a, b)` is a binary predicate: `true` if `a` is ordered before `b`. Defaults to `(a, b) => a < b`. The `Less<T>` type names this shape.
- Preconditions: the array is sorted compatibly with `less`, and `value` is comparable with the elements under `less`.
- Equality is derived from the ordering: `a` and `b` are equal when neither is less than the other. Each equality test costs one extra `less` call after the search — the search itself already guarantees one direction.
- Queries take `readonly` arrays and accept optional `l`/`r` sub-range bounds; mutators require mutable arrays and operate on the whole array.

Queries:

- `lowerBound(sortedArray, value, less?, l?, r?)` → the index of the first element ≥ `value`. Inserting there places `value` before any equal elements.
- `upperBound(sortedArray, value, less?, l?, r?)` → the index of the first element > `value`. Inserting there places `value` after any equal elements.
- `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 half-open span `[lo, hi)` of equal elements (C++ `std::equal_range`). An absent value yields an empty span (`lo === hi`) at its insertion point. `sortedArray.splice(lo, hi - lo)` removes all equal elements and keeps the array sorted.
- `count(sortedArray, value, less?, l?, r?)` → the number of equal elements.

Mutators:

- `insert(sortedArray, value, less?)` → inserts `value` keeping the array sorted — at the upper bound, after any equal elements, matching Python's `bisect.insort`. Returns the insertion index.
- `remove(sortedArray, value, less?)` → removes the first element equal to `value`. Returns `true` if an element was removed.
- `removeAll(sortedArray, value, less?)` → removes all elements equal to `value`. Returns the number removed.

### Guarantees

- Every returned index is in `[l, r]` and is a valid `splice()` index — empty arrays, out-of-range pivots, duplicate values, and sub-ranges included.
- Inserting at a returned bound preserves sort order; the mutators preserve the sorted-array invariant unconditionally.
- Complexity: O(log n) calls to `less` per search, plus at most one equality check; queries allocate nothing (`equalRange` allocates its result pair).

## Usage

ESM:

```js
import binarySearch from 'nano-binary-search';
import {indexOf, includes, insert, remove, removeAll} from 'nano-binary-search';
```

CommonJS (Node 22.12+ `require()` of ESM):

```js
const {binarySearch, indexOf, insert} = require('nano-binary-search');
```

TypeScript (types resolve via the `@ts-self-types` directive; `LessFn` and `Less` are exported):

```ts
import binarySearch, {type Less, indexOf} from 'nano-binary-search';

const byId: Less<{id: number}> = (a, b) => a.id < b.id;
const index: number = indexOf(items, {id: 42}, byId);
```

## Recipes

With the ready-made functions:

```js
insert(sortedArray, value); // insert keeping sorted order
remove(sortedArray, value); // remove the first equal element
removeAll(sortedArray, value); // remove all equal elements
const present = includes(sortedArray, value);
const n = count(sortedArray, value);
```

The same operations with the raw primitive (useful when the closure captures more than a value):

```js
// Find insertion point (lower bound): index of first element >= value
const index = binarySearch(sortedArray, x => x < value);
sortedArray.splice(index, 0, value); // insert keeping sorted order

// Find upper bound: index of first element > value
const upper = binarySearch(sortedArray, x => x <= value);

// Find and 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);

// Search a sub-range only: pass the bounds
const inRange = binarySearch(sortedArray, x => x < value, 10, 20);
```

### Examples with results

```js
binarySearch([1, 2, 4, 5], x => x < 3); // → 2 (insert 3 at index 2)
binarySearch([1, 2, 4, 5], x => x <= 2); // → 2 (upper bound of 2)
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)

indexOf([1, 3, 3, 5], 3); // → 1 (first of the run)
lastIndexOf([1, 3, 3, 5], 3); // → 2
includes([1, 3, 3, 5], 4); // → false
equalRange([1, 3, 3, 5], 3); // → [1, 3]
count([1, 3, 3, 5], 3); // → 2

const a = [1, 3, 3, 5];
insert(a, 4); // → 3; a is [1, 3, 3, 4, 5]
remove(a, 4); // → true; a is [1, 3, 3, 5]
removeAll(a, 3); // → 2; a is [1, 5]
```

## Related: keeping sort and search in sync

The sorted array must be sorted in a way compatible with `less`. The clean way to enforce that is to derive both the sort comparator and the search predicate from a single source. [`meta-toolkit/comparators`](https://github.com/uhop/meta-toolkit) ships the adapters:

- `lessFromCompare(compareFn)` — `(a, b) => boolean` from a sort-style comparator. Use when you already have a `compareFn` for `Array.prototype.sort()`.
- `compareFromLess(lessFn)` — the inverse; build a `sort()`-compatible comparator from a `less` function.
- `reverseLess(lessFn)` / `reverseCompare(compareFn)` — descending order.
- `equalFromLess(lessFn)` — derived equality (for membership checks alongside the search).

The derived predicate plugs straight into every value-based function:

```js
import {indexOf, insert} from 'nano-binary-search';
import {lessFromCompare} from 'meta-toolkit/comparators';

const less = lessFromCompare(compareFn); // build once
sortedArray.sort(compareFn); // sort with compareFn
const idx = indexOf(sortedArray, value, less); // search with the derived less
insert(sortedArray, newValue, less); // insert with it too
```

`nano-binary-search` has zero runtime dependencies — `meta-toolkit` is a documented companion, not a requirement.