Binary Search

# Binary Search

Zerethon Official Sample `binary-search`, version 1.5.0, Node.js 22.

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

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. */
function binarySearch(a, target) {
    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;
}

/** Every comparison binarySearch makes, as [lo, mid, hi]. */
function binarySearchSteps(a, target) {
    const steps = [];
    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;
}

module.exports = { binarySearch, binarySearchSteps };

const { binarySearch, binarySearchSteps } = require('./binary_search');

const numbers = [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.
const assert = require('assert');
const { binarySearch } = require('./binary_search');

const range = Array.from({ length: 500 }, (_, i) => i * 2);
const cases = [
    [[], 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) {
    assert.strictEqual(binarySearch(a, target), expected, `binarySearch([${a.slice(0, 5)}...], ${target})`);
}

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