Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C

Binary search and lower bound in C

Binary search halves a sorted search range repeatedly. The example implements lower bound: the index of the first element not less than the key, or n if none exists. It covers duplicates, empty input, and safe midpoint calculation.

Version: C23; repository compiler flag, production runtime not attested

Syntax

size_t lower_bound_int(const int *a, size_t n, int key);

Binary search selects the middle of a range and discards the half that cannot contain the required result. The sorted input precondition here means that a[0..n) is sorted in nondecreasing order using the same comparison as the search. The function does not check this condition; unsorted input can produce an incorrect result.

The example function lower_bound_int implements lower bound: it returns the first index pos for which a[pos] >= key, or n if none exists. With duplicates, it identifies the first occurrence. The index alone does not establish membership: use pos < n && a[pos] == key. Short-circuit evaluation prevents this test from reading a[n].

The loop maintains the half-open range [lo, hi): elements before lo are less than key, and elements from hi up to n are not less than key. The statement hi = mid retains a possible first result, whereas lo = mid + 1 skips an element that is too small. The expression lo + (hi - lo) / 2 avoids overflow from adding the endpoints. When lo == hi, both boundaries identify the result.

For n > 0, a must provide at least n valid elements; they must not change during the search. For n == 0, this implementation accepts NULL and returns 0 without reading memory. On an array, time is O(log n) for n >= 2 and auxiliary space is O(1); prior sorting is not included. C23 is the repository compiler-flag target, not an attestation of the production runtime.

Examples

#include <stddef.h>
#include <stdio.h>

static size_t lower_bound_int(const int *a, size_t n, int key)
{
    size_t lo = 0;
    size_t hi = n;

    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

int main(void)
{
    const int a[] = {1, 3, 3, 7};
    const size_t n = sizeof a / sizeof a[0];
    const int keys[] = {3, 4, 9};

    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
        size_t pos = lower_bound_int(a, n, keys[i]);
        int found = pos < n && a[pos] == keys[i];
        printf("key=%d pos=%zu found=%d\n", keys[i], pos, found);
    }
    printf("empty pos=%zu\n", lower_bound_int(NULL, 0, 3));
    return 0;
}

Result

key=3 pos=1 found=1
key=4 pos=3 found=0
key=9 pos=4 found=0
empty pos=0

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources