Binary Search in C: First Match, Iteration and Recursion

Binary search in C halves a sorted search interval until it finds a target or proves it absent. These two programs return the first matching index when duplicates exist, or the array length when absent. Input must already be sorted in ascending order; use linear search for unsorted data.

Iterative first-match program

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

size_t binary_search(const int values[], size_t count, int target) {
    size_t low = 0, high = count;
    while (low < high) {
        size_t mid = low + (high - low) / 2;
        if (values[mid] < target) low = mid + 1;
        else high = mid;
    }
    return low < count && values[low] == target ? low : count;
}

int main(void) {
    int values[] = {2, 4, 4, 7, 9};
    size_t count = sizeof values / sizeof values[0];
    size_t index = binary_search(values, count, 4);
    if (index == count) puts("Not found");
    else printf("First match: index %zu\n", index);
    return 0;
}

First match: index 1

Dry run with duplicate values

For 2 4 4 7 9, target 4, the interval is [low, high): low is included and high is excluded. High may equal count and must never be indexed.

The loop locates the first value that is not smaller than the target. A final bounds-and-equality check distinguishes a match from an insertion position. Returning immediately on equality would find an arbitrary matching index rather than the first one. The midpoint low + (high - low) / 2 avoids overflowing by adding low and high directly.

Recursive version with the same contract

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

static size_t lower_bound(const int values[], size_t low, size_t high, int target) {
    if (low == high) return low;
    size_t mid = low + (high - low) / 2;
    if (values[mid] < target) return lower_bound(values, mid + 1, high, target);
    return lower_bound(values, low, mid, target);
}

size_t binary_search_recursive(const int values[], size_t count, int target) {
    size_t index = lower_bound(values, 0, count, target);
    return index < count && values[index] == target ? index : count;
}

int main(void) {
    int values[] = {2, 4, 4, 7, 9};
    size_t count = sizeof values / sizeof values[0];
    size_t index = binary_search_recursive(values, count, 4);
    if (index == count) puts("Not found");
    else printf("First match: index %zu\n", index);
    return 0;
}

First match: index 1

The helper carries the same half-open interval. For target 4 its calls narrow from [0,5) to [0,2), [0,1) and [1,1). The base case returns an insertion position; the wrapper checks for an actual match. There is no mid - 1 underflow when mid is zero.

Preconditions, empty input and missing values

For a positive count, supply that many readable sorted integers. With count zero, a null pointer is permitted: no element is read and the absent sentinel is zero. Do not use a nonstandard zero-length array. The returned sentinel must be checked before indexing, including in the empty case. These functions do not sort or validate the input order on every call; doing so would erase the logarithmic query advantage.

Try target 2 (index 0), 9 (index 4), 3 (absent), 1 (absent), and 10 (absent). In an all-equal array the matching index is zero. Negative values and integer extremes work because comparisons do not subtract integers. No stdin is needed: change the array and target in the displayed program.

Complexity and choosing a search

Both forms take O(log n) comparisons in the worst case on a random-access array. The iterative version uses O(1) auxiliary space. The recursive version uses O(log n) call-stack space without assuming tail-call optimization. Unlike an equality-return variant, this first-match version keeps narrowing after an equal comparison.

Sorting solely to answer one query usually costs more than one O(n) linear scan. Sorting once can make sense for many queries; see the sorting comparison. Binary search over a linked list does not inherit an array's constant-time midpoint access.

Practice and answers

For 1 3 3 3 8, target 3: [0,5) → [0,2) → [0,1) → [1,1), result 1. For target 6, the insertion position is 4 but value 8 is not a match, so return count (5). To find the last duplicate, use an upper-bound search and carefully check the preceding element; simply changing one return statement is not enough.

Is binary search safe on unsorted arrays?

The accesses still obey the supplied bounds, but the search result can be wrong. Sorted order is a correctness precondition, not an optional optimization.