Repository
Current version released
3 years ago
Versions
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);