Binary Search

# Binary Search

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

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

Run compiles the entry file together with every other `.c` 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.h"

int binary_search(const int *a, size_t n, int target) {
    int lo = 0;
    int hi = (int) n - 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;
}

size_t binary_search_steps(const int *a, size_t n, int target, int steps[][3], size_t max_steps) {
    size_t count = 0;
    int lo = 0;
    int hi = (int) n - 1;
    while (lo <= hi && count < max_steps) {
        int mid = lo + (hi - lo) / 2;
        steps[count][0] = lo;
        steps[count][1] = mid;
        steps[count][2] = hi;
        count++;
        if (a[mid] == target) break;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return count;
}

// Binary search over a sorted array (Zerethon Official Sample: binary-search 1.4.0).
#ifndef BINARY_SEARCH_H
#define BINARY_SEARCH_H

#include <stddef.h>

/* Return the index of target in a[0..n) (sorted ascending), or -1 if it is absent. */
int binary_search(const int *a, size_t n, int target);

/* Write every comparison binary_search makes as {lo, mid, hi} into steps; return the count. */
size_t binary_search_steps(const int *a, size_t n, int target, int steps[][3], size_t max_steps);

#endif

#include <stdio.h>
#include "binary_search.h"

int main(void) {
    const int numbers[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    const size_t n = sizeof numbers / sizeof numbers[0];

    printf("Sorted list: [");
    for (size_t i = 0; i < n; i++) printf(i ? ", %d" : "%d", numbers[i]);
    printf("]\n\n");

    const int targets[] = {23, 2, 91, 7};
    for (size_t i = 0; i < 4; i++) {
        int index = binary_search(numbers, n, targets[i]);
        if (index != -1) printf("search %2d: found at index %d\n", targets[i], index);
        else printf("search %2d: not found\n", targets[i]);
    }

    int steps[32][3];
    size_t count = binary_search_steps(numbers, n, 23, steps, 32);
    printf("\nSteps for 23 (lo, mid, hi):\n");
    for (size_t i = 0; i < count; i++) {
        printf("  lo=%d mid=%d hi=%d -> a[mid]=%d\n", steps[i][0], steps[i][1], steps[i][2], numbers[steps[i][1]]);
    }
    return 0;
}

// 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 <stdio.h>
#include "binary_search.h"

static int checks = 0;
static int failed = 0;

static void check(const int *a, size_t n, int target, int expected) {
    int actual = binary_search(a, n, target);
    checks++;
    if (actual != expected) {
        fprintf(stderr, "binary_search(length %zu, %d): expected %d, got %d\n", n, target, expected, actual);
        failed++;
    }
}

int main(void) {
    int range[500];
    for (int i = 0; i < 500; i++) range[i] = i * 2;
    const int one[] = {4};
    const int odd[] = {1, 3, 5, 7, 9};

    check(NULL, 0, 1, -1);
    check(one, 1, 4, 0);
    check(one, 1, 5, -1);
    check(odd, 5, 1, 0);
    check(odd, 5, 9, 4);
    check(odd, 5, 6, -1);
    check(range, 500, 998, 499);

    if (failed) return 1;
    printf("All %d checks passed.\n", checks);
    return 0;
}