Binary search in C: first occurrence and bounds

Your array is sorted, but your binary search misses the last element or gets stuck on two cells. Then you add duplicates: finding a 4 is no longer enough. You want the first one.

What do lo and hi represent?

[lo, hi) holds the indexes still to examine: lo is included and hi is excluded. For seven elements, start with [0, 7). The last readable index is still 6. Position 7 is a boundary, never a cell to read.

This is the array we'll search. All three 4 values are equal, but only index 1 answers the question "where does this run begin?"

The array must be sorted in ascending order, with duplicates allowed. The algorithm relies on that order to discard values without reading them. It doesn't check the sort order on each search: walking the whole array to verify it would already take linear time.

How do the bounds narrow when searching for 4?

The first comparison reads index 3, which holds 4. Setting hi = 3 leaves room to find an earlier 4. Equality doesn't end the search.

"Outside range" means the loop no longer needs to examine that cell. The hi boundary can still be the answer's position: the next step only checks whether an earlier position qualifies. The precise invariant is that everything before lo is less than key, and everything from hi onward is greater than or equal to key. The loop locates the boundary between those two regions.

What C code handles duplicates and an empty array?

This function returns the first matching index, or n when the value is missing. That keeps its result in size_t: there's no -1 to convert to an unsigned integer.

#include <stddef.h>#include <stdio.h>
static size_t first_equal(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 < n && a[lo] == key ? lo : n;}
static void show(const int a[], size_t n, int key){    size_t index = first_equal(a, n, key);    if (index == n)        printf("key=%d: not found\n", key);    else        printf("key=%d: index=%zu\n", key, index);}
int main(void){    int values[] = {2, 4, 4, 4, 7, 9, 12};    size_t n = sizeof values / sizeof values[0];
    show(values, n, 4);    show(values, n, 6);    show(values, n, 2);    show(values, n, 12);    show(NULL, 0, 4);    return 0;}

$ gcc -std=c17 -Wall -Wextra -Werror search.c -o search$ ./searchkey=4: index=1key=6: not foundkey=2: index=0key=12: index=6key=4: not found

n must be the number of elements actually accessible through a. For n > 0, the pointer must refer to that array. With n == 0, the loop doesn't start, and the final && stops after lo < n evaluates to false: it doesn't evaluate a[lo]. That's why this program can call first_equal(NULL, 0, 4).

The value 6 exposes another trap: the loop finds its insertion position, index 4, which holds 7. Only the final equality check lets you report "not found." If the target exceeds every value, lo becomes n and no cell is read.

Why use mid + 1 on one side and mid on the other?

When a[mid] < key, index mid is too small and must leave the search range. When a[mid] >= key, it might mark the start of the greater-or-equal region, so it becomes the right boundary.

With lo < hi, the midpoint satisfies lo <= mid < hi. Both branches strictly reduce hi - lo. Writing lo = mid can stall: when one cell remains, mid == lo and the boundary stops moving. Writing hi = mid - 1 mixes an inclusive right bound with the convention used here. With size_t, subtracting 1 from zero also produces a very large unsigned value.

The formula lo + (hi - lo) / 2 avoids computing lo + hi, whose sum can exceed the type's range. Under the invariant lo <= hi, the subtraction is valid and the result cannot exceed hi.

binary_search

Adapt this reasoning to a sequence accessed through the at(i) callback. The exercise asks for the first index, a return value of -1 when missing, and at most 24 reads for a million elements. Its contract differs from first_equal: follow the supplied signature and count the final verification read too.

Open the exercise

When should you use bsearch or a linear search?

bsearch, declared in <stdlib.h>, works when you want a pointer to any matching occurrence. With equal elements, it doesn't guarantee the first one. Its comparator uses the negative, zero, positive convention explained in the qsort article.

On an array with direct element access, our loop makes O(log n) comparisons and uses O(1) extra space. Sorting an array just to search it once doesn't automatically pay off: a linear search may suffice. An already sorted array searched frequently is a good fit for binary search. The distinction between an array and a pointer, which affects how you compute n, is covered in Array or pointer in C.

Frequently asked questions