C Basics: Find a Record in a Sorted Array with bsearch

A read-only lookup table can use binary search when its records are ordered by the same key used by the search callback. Keep the key and record types explicit.

Prepare a scratch directory

Tested on Linux x86_64 with GCC 14.2.0. Install GCC and the C standard-library development headers, and make gcc available on PATH. You also need Bash, a text editor, and mktemp, rm, and rmdir. No third-party C library is required.

Keep the same terminal open. Stop if setup fails, before saving the source:

start_directory="$PWD"
work_directory="$(mktemp -d)" || exit 1
cd -- "$work_directory" || exit 1

Run the example

Save this as bsearch-sorted-records-demo.c:

#include <stdio.h>
#include <stdlib.h>

struct service_record {
    int code;
    const char *name;
};

static int compare_key_to_record(const void *key_pointer, const void *record_pointer)
{
    const int key = *(const int *)key_pointer;
    const struct service_record *record = record_pointer;
    return (key > record->code) - (key < record->code);
}

int main(void)
{
    const struct service_record services[] = {
        {10, "storage"}, {20, "search"}, {30, "reports"}
    };
    const int requested_codes[] = {20, 25};
    const size_t count = sizeof services / sizeof services[0];
    for (size_t index = 0; index < sizeof requested_codes / sizeof requested_codes[0]; ++index) {
        const struct service_record *found = bsearch(
            &requested_codes[index], services, count, sizeof services[0],
            compare_key_to_record);
        printf("Code %d: %s\n", requested_codes[index], found != NULL ? found->name : "missing");
    }
    return 0;
}

Compile and run it. The && prevents execution if compilation fails:

gcc -std=c17 -Wall -Wextra -Werror -pedantic bsearch-sorted-records-demo.c -o bsearch-sorted-records-demo &&
./bsearch-sorted-records-demo

Observed output:

Code 20: search
Code 25: missing

Read the result

The callback receives the search key first and an array element second. The table is already sorted by code, so the same comparison partitions it correctly. A missing key returns NULL, which is checked before any dereference.

Apply it carefully

Do not apply this callback to an unsorted table. If matching keys repeat, bsearch may return any matching element, not necessarily the first. The returned pointer refers to the existing array; it does not allocate a copy and must not outlive that array.

The GNU reference documents the relevant interface or language rules.

Clean up

Remove only the source and executable created here, then remove the empty practice directory:

rm -- bsearch-sorted-records-demo.c bsearch-sorted-records-demo
cd -- "$start_directory" || exit 1
rmdir -- "$work_directory"
unset start_directory work_directory

If the directory is not empty, inspect the remaining contents before removing anything else.

Acknowledgements

This post was created with assistance from AI.