Binary search in TypeScript
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
binarySearch.ts, 18 lines- Level
- Native tests
- pass in this build
- Toolchain
- TypeScript 5, strict, run by Node.js 24 type stripping
- Test framework
- node:test
- Run the tests
node --test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
/** Returns an index i with a[i] === x, or -1 when x is not in a. The array must be sorted. */
export function binarySearch<T>(a: readonly T[], x: T): number {
let lo = 0, hi = a.length; // @line L1
while (lo < hi) { // @line L2
const mid = lo + ((hi - lo) >> 1); // @line L3
if (a[mid] < x) { // @line L4
lo = mid + 1; // @line L5
} else if (a[mid] > x) { // @line L6
hi = mid; // @line L7
} else {
return mid; // @line L8
}
}
return -1; // @line L9
}
binarySearch.test.ts 37 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
import { test } from "node:test";
import assert from "node:assert/strict";
import { binarySearch } from "./binarySearch.ts";
test("examples", () => {
const a = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
assert.equal(binarySearch(a, 23), 5);
assert.equal(binarySearch(a, 2), 0);
assert.equal(binarySearch(a, 91), 9);
assert.equal(binarySearch(a, 30), -1);
assert.equal(binarySearch(a, 1), -1);
assert.equal(binarySearch(a, 100), -1);
});
test("edges", () => {
assert.equal(binarySearch([], 1), -1);
assert.equal(binarySearch([7], 7), 0);
assert.equal(binarySearch(["ant", "bee", "cat"], "bee"), 1);
});
test("random against a linear scan", () => {
let s = 2150;
const next = (m: number): number => {
s = (Math.imul(s, 1103515245) + 12345) >>> 0;
return (s >>> 8) % m;
};
for (let t = 0; t < 2000; t++) {
const a = Array.from({ length: next(31) }, () => next(41) - 20).sort((p, q) => p - q);
const x = next(51) - 25;
const i = binarySearch(a, x);
if (a.includes(x)) assert.equal(a[i], x);
else assert.equal(i, -1);
}
});
What the next level needs
- I2 needs the differential and mutation runs (09.5, 09.6), which are M1 work