Binary Search in C Using the bsearch Function

The bsearch function, defined in the standard <stdlib.h> header, provides a generic implementation of the binary search algorithm in the C programming language. It efficiently locates a target item within a contiguous, pre-sorted memory buffer in logarithmic time (\(O(\log n)\)). This article breaks down how bsearch works under the hood, how it handles generic memory addresses using pointer arithmetic, and how it interacts with user-defined comparison callbacks.

Function Signature and Parameters

The standard signature for bsearch is:

void *bsearch(const void *key,
              const void *base,
              size_t nmemb,
              size_t size,
              int (*compar)(const void *, const void *));

The function accepts five arguments:

• key: A pointer to the element you want to find.
• base: A pointer to the first byte of the sorted array in memory.
• nmemb: The total count of elements in the array.
• size: The size in bytes of an individual element (sizeof(...)).
• compar: A pointer to a comparison function that dictates the ordering logic.

Memory Navigation with Generic Pointers

Because bsearch operates on void * pointers, the compiler does not know the concrete data type stored in the buffer. To inspect individual elements, bsearch uses byte-level pointer arithmetic using the size parameter.

To calculate the memory address of an element at index mid, the function internally offsets from the base pointer using byte casting:

\[\text{element\_address} = (\text{const char *})\text{base} + (\text{mid} \times \text{size})\]

Casting base to const char * ensures that addition advances memory one byte at a time. Multiplying the index by size advances the pointer by the exact byte length of each element, allowing bsearch to work seamlessly with native types, structs, or custom data structures.

The Search Execution Loop

Once initialized, bsearch executes the classic binary search algorithm across the indices:

1. Calculate Midpoint: The search boundary begins with indices low = 0 and high = nmemb - 1. During each iteration, the midpoint index is calculated: mid = low + (high - low) / 2.

2. Invoke Comparator: The function computes the address of the element at mid and passes key and the middle element to the compar function:

   int result = compar(key, (const char *)base + (mid * size));

3. Adjust Search Space:

   • If result < 0: The target key is smaller than the middle element. The search interval shrinks to the left half by setting high = mid - 1.
   • If result > 0: The target key is larger than the middle element. The search interval shrinks to the right half by setting low = mid + 1.
   • If result == 0: A match is found. bsearch immediately returns a generic pointer (void *) to the matching element.

4. Termination: If low exceeds high without a match, the loop terminates and the function returns NULL.

The Comparator Contract

The caller must supply a comparison function that mirrors the sorting order of the array. The comparator must accept two const void * arguments: the first argument is always the key pointer passed into bsearch, and the second argument is a pointer to the current array element being evaluated.

The callback must return:

• An integer less than 0 if key precedes the array element.
• An integer greater than 0 if key follows the array element.
• Exactly 0 if both elements are equal according to the search criteria.

Usage Constraints and Behavior

• Strict Pre-Sorting: The memory buffer must already be sorted in ascending order relative to the provided comparator. If the buffer is unsorted, the behavior of bsearch is undefined, and it may return NULL even if the element exists.
• Handling Duplicates: If the memory buffer contains multiple elements that match key (where the comparator returns 0), the C standard does not specify which duplicate element will be returned.
• Type Safety: Because bsearch returns a void *, the calling code must cast the return value back to the appropriate data type before dereferencing it.