binary_search

The binary search algorithm implemented in TypeScript for Deno.

Motivation

Sometimes one needs O(log n) search performance.

mod.ts

The find function can be used to find an item in an array. The array must be sorted according to the compare function.

import { find } from "https://deno.land/x/binary_search/mod.ts";

const array = ["a", "b", "c", "d", "e"];
const compare = (a: string, b: string) => a.charCodeAt(0) - b.charCodeAt(0);
const index = find(array, "c", compare);

console.assert(index === 2);

If the item is not in the array, a negative number is is returned. The complement of that number is the index at which one would have to insert the item to preserve the order.

import { find } from "https://deno.land/x/binary_search/mod.ts";

const array = [0, 1, 2, 3, 4];
const index = find(array, 2.5, (a, b) => a - b);

console.assert(index === -4);
console.assert(~index === 3);

The findNumber function is a special case of find for searching a number in an ordered sequence of numbers.

import { findNumber } from "https://deno.land/x/binary_search/mod.ts";

const array = [0, 1, 2, 3, 4];
const index = findNumber(array, 2);

console.assert(index === 2);