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.