Binary Search

# Binary Search

Zerethon Official Sample `binary-search`, version 1.5.0, TypeScript 7 (Node.js 22).

- `binary_search.ts` — the algorithm (`binarySearch`, and `binarySearchSteps` to trace it)
- `main.ts` — entry file: searches a few values and prints the steps
- `test_binary_search.ts` — checks; set it as the entry file to run them

Every `.ts` file is type-checked (`--strict`) before anything runs; a type error stops the run.

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/binary-search-visualizer

// Binary search over a sorted array (Zerethon Official Sample: binary-search 1.5.0).

/** Return the index of target in a (sorted ascending), or -1 if it is absent. */
export function binarySearch(a: readonly number[], target: number): number {
    let lo = 0;
    let hi = a.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (a[mid] === target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

export type Step = [lo: number, mid: number, hi: number];

/** Every comparison binarySearch makes, as [lo, mid, hi]. */
export function binarySearchSteps(a: readonly number[], target: number): Step[] {
    const steps: Step[] = [];
    let lo = 0;
    let hi = a.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        steps.push([lo, mid, hi]);
        if (a[mid] === target) break;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return steps;
}

import { binarySearch, binarySearchSteps } from './binary_search';

const numbers: number[] = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(`Sorted list: [${numbers.join(', ')}]`);
console.log();

for (const target of [23, 2, 91, 7]) {
    const index = binarySearch(numbers, target);
    const result = index !== -1 ? `found at index ${index}` : 'not found';
    console.log(`search ${String(target).padStart(2)}: ${result}`);
}

console.log();
console.log('Steps for 23 (lo, mid, hi):');
for (const [lo, mid, hi] of binarySearchSteps(numbers, 23)) {
    console.log(`  lo=${lo} mid=${mid} hi=${hi} -> a[mid]=${numbers[mid]}`);
}

// Checks for binarySearch. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
import { strictEqual } from 'assert';
import { binarySearch } from './binary_search';

const range = Array.from({ length: 500 }, (_, i) => i * 2);
const cases: [number[], number, number][] = [
    [[], 1, -1],
    [[4], 4, 0],
    [[4], 5, -1],
    [[1, 3, 5, 7, 9], 1, 0],
    [[1, 3, 5, 7, 9], 9, 4],
    [[1, 3, 5, 7, 9], 6, -1],
    [range, 998, 499],
];

for (const [a, target, expected] of cases) {
    strictEqual(binarySearch(a, target), expected, `binarySearch([${a.slice(0, 5)}...], ${target})`);
}

console.log(`All ${cases.length} checks passed.`);