Binary search implemented in C99 with visualization

binsearch.c

/* SPDX-License-Identifier: Unlicense */

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEN 20
#define LENOF(str) ((sizeof str) - 1)

static int snprint_arr(
        int const * const arr, size_t const arrlen, char *const buf, size_t const bufsize)
{
    int written = snprintf(buf, bufsize, "[");
    for (size_t i = 0;;) {
        written += snprintf(buf + written, bufsize - written, "%d", arr[i]);
        if ((size_t)written + 1 >= bufsize) {
            return written;
        }
        i++;
        if (i < arrlen) {
            written += snprintf(buf + written, bufsize - written, ", ");
            if ((size_t)written + 1 >= bufsize) {
                return written;
            }
        } else {
            break;
        }
    }
    written += snprintf(buf + written, bufsize - written, "]");
    return written;
}

static void print_binsearch_state(
        int const * const arr,
        size_t const arrlen,
        int const value,
        size_t const start,
        size_t const middle,
        size_t const len)
{
    char buf[81] = {'\0'};
    snprint_arr(arr, arrlen, buf, 81);
    printf("%s\n", buf);
    int const written_to_start = snprint_arr(arr, start, buf, 81) + LENOF(", ");
    int const written_to_middle = (middle == start)
        ? written_to_start
        : snprint_arr(arr, middle, buf, 81) + (int)LENOF(", ");
    int const written_len = snprint_arr(arr, start + len, buf, 81);
    printf("%*s", written_to_start, "^");
    for (size_t i = 0; i < 80; i++) {
        buf[i] = '~';
    }
    buf[80] = '\0';
    if (written_to_middle != written_to_start) {
        int const span_before_middle = written_to_middle - written_to_start - LENOF("^");
        printf("%.*s^", span_before_middle, buf);
        int const span_after_middle = written_len - written_to_middle - LENOF("^");
        printf("%.*s", span_after_middle, buf);
    } else {
        int const span = written_len - written_to_start - LENOF("^");
        printf("%.*s", span, buf);
    }
    printf("\n");
    if (written_to_middle != written_to_start) {
        int const span_before_middle = written_to_middle - written_to_start;
        printf("%*s%*s", written_to_start, "s", span_before_middle, "m");
    } else {
        printf("%*s", written_to_start, "s/m");
    }
    const char *const sign = (arr[middle] > value) ? ">" : ((arr[middle] < value) ? "<" : "==");
    printf(" %s %d\n", sign, value);
}

static size_t binsearch(
        int const * const arr,
        size_t const arrlen,
        int const value,
        bool const visualize)
{
    if (arrlen == 0) {
        return 0;
    }
    size_t start = 1, len = arrlen - start, index = 0;
    while (1) {
        if (len == 0) {
            break;
        }
        size_t const middle = start + len / 2;
        if (visualize) {
            print_binsearch_state(arr, arrlen, value, start, middle, len);
        }
        if (arr[middle] >= value) {
            if (arr[middle] == value) {
                index = middle;
            }
            // Look at the span right before the middle one on the next step
            len = middle - start;
        } else {
            // Look at the span right after the middle one on the next step
            len -= middle + 1 - start;
            start = middle + 1;
        }
    }
    return index;
}

static int cmp(void const *p1, void const *p2)
{
    return *(int const *)p1 - *(int const *)p2;
}

static void run_random_visualization(void)
{
    int arr[LEN] = {0};
    for (size_t i = 1; i < LEN; i++) {
        arr[i] = rand() % LEN;
    }
    qsort(arr, LEN, sizeof *arr, cmp);
    int const search = rand() % LEN;
    size_t const index = binsearch(arr, LEN, search, true);
    if (index == 0) {
        printf("%d is not found\n", search);
    } else {
        printf("%d is found at index %zu\n", search, index);
    }
}

static void print_arr(int const * const arr, size_t const arrlen)
{
    printf("[");
    for (size_t i = 0;;) {
        printf("%d", arr[i]);
        i++;
        if (i < arrlen) {
            printf(", ");
        } else {
            break;
        }
    }
    printf("]\n");
}

static void run_random_tests(size_t const tests_count, size_t const arrlen)
{
    int *arr = calloc(sizeof (int), arrlen);
    if (arr == NULL) {
        fprintf(stderr, "Falied to calloc(%zu, %zu)\n", sizeof *arr, arrlen);
        exit(EXIT_FAILURE);
    }
    arr[0] = 0;
    for (size_t t = 0; t < tests_count; t++) {
        for (size_t i = 1; i < arrlen; i++) {
            arr[i] = rand() % (int)arrlen;
        }
        qsort(arr, arrlen, sizeof *arr, cmp);
        int const search = rand() % (int)arrlen;
        size_t const index = binsearch(arr, arrlen, search, false);
        if (index == 0) {
            for (size_t i = 1; i < arrlen; i++) {
                if (arr[i] == search) {
                    print_arr(arr, arrlen);
                    printf("Test %zu failed: arr[i] == search, index=%zu, i=%zu, search=%d\n", t, index, i, search);
                    exit(EXIT_FAILURE);
                }
            }
        } else {
            if (arr[index] != search) {
                print_arr(arr, arrlen);
                printf("Test %zu failed: arr[index] != search, index=%zu, search=%d\n", t, index, search);
                exit(EXIT_FAILURE);
            }
            if (index > 1) {
                if (arr[index - 1] == search) {
                    print_arr(arr, arrlen);
                    printf("Test %zu failed: arr[index - 1] != search, index=%zu, search=%d\n", t, index, search);
                    exit(EXIT_FAILURE);
                }
            }
        }
    }
    free(arr);
    printf("%zu tests of arrlen=%zu have passed successfully\n", tests_count, arrlen);
}

int main(int argc, char * const argv[])
{
    (void)argv;
    unsigned const seed = time(NULL);
    printf("seed=%u\n", seed);
    srand(seed);
    if (argc > 1) {
        run_random_tests(10000, 1000);
    } else {
        run_random_visualization();
    }
}