Binary Search

# Binary Search

Zerethon Official Sample `binary-search`, version 1.5.0, C++ (GCC 14).

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

Run compiles the entry file together with every other `.cpp` file except other programs (files
whose name starts with `main` or `test_`).

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

#include "binary_search.hpp"

int binary_search(const std::vector<int> &a, int target) {
    int lo = 0;
    int hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

std::vector<std::array<int, 3>> binary_search_steps(const std::vector<int> &a, int target) {
    std::vector<std::array<int, 3>> steps;
    int lo = 0;
    int hi = static_cast<int>(a.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        steps.push_back({lo, mid, hi});
        if (a[mid] == target) break;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return steps;
}

// Binary search over a sorted vector (Zerethon Official Sample: binary-search 1.5.0).
#pragma once
#include <array>
#include <vector>

// Return the index of target in a (sorted ascending), or -1 if it is absent.
int binary_search(const std::vector<int> &a, int target);

// Every comparison binary_search makes, as {lo, mid, hi}.
std::vector<std::array<int, 3>> binary_search_steps(const std::vector<int> &a, int target);

#include <iomanip>
#include <iostream>
#include <vector>
#include "binary_search.hpp"

int main() {
    const std::vector<int> numbers = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    std::cout << "Sorted list: [";
    for (size_t i = 0; i < numbers.size(); i++) std::cout << (i ? ", " : "") << numbers[i];
    std::cout << "]\n\n";

    for (int target : {23, 2, 91, 7}) {
        int index = binary_search(numbers, target);
        std::cout << "search " << std::setw(2) << target << ": ";
        if (index != -1) std::cout << "found at index " << index << '\n';
        else std::cout << "not found\n";
    }

    std::cout << "\nSteps for 23 (lo, mid, hi):\n";
    for (const auto &[lo, mid, hi] : binary_search_steps(numbers, 23)) {
        std::cout << "  lo=" << lo << " mid=" << mid << " hi=" << hi << " -> a[mid]=" << numbers[mid] << '\n';
    }
}

// Checks for binary_search. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
#include <iostream>
#include <tuple>
#include <vector>
#include "binary_search.hpp"

int main() {
    std::vector<int> range;
    for (int i = 0; i < 500; i++) range.push_back(i * 2);
    const std::vector<std::tuple<std::vector<int>, int, int>> 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 auto &[a, target, expected] : cases) {
        int actual = binary_search(a, target);
        if (actual != expected) {
            std::cerr << "binary_search(length " << a.size() << ", " << target << "): expected " << expected << ", got " << actual << '\n';
            return 1;
        }
    }
    std::cout << "All " << cases.size() << " checks passed." << std::endl;
}