C Binary Search

Binary search is a fast algorithm for finding a value inside a sorted array by repeatedly cutting the search space in half. Instead of checking every element one by one like linear search, it jumps straight to the middle of the remaining range, decides whether the target is smaller or larger, and throws away half of the remaining data on every single comparison. Because of this halving strategy, binary search can find an element in a sorted array of a million items using only about twenty comparisons, instead of up to a million. It is one of the first algorithms every C programmer should master, both because it teaches divide-and-conquer thinking and because it shows up everywhere in real code, including inside the C standard library itself.

Overview: How Binary Search Works

Binary search only works correctly on data that is already sorted, normally in ascending order. The algorithm tracks a search window with two indices, conventionally called low and high, which mark the leftmost and rightmost positions that could still contain the target value. On each iteration it computes the index exactly in the middle of that window, mid, and compares the value stored there with the target.

There are exactly three possible outcomes of that comparison:

• If arr[mid] equals the target, the search is done — return mid.
• If arr[mid] is less than the target, the target (if present) must be to the right, so the window shrinks to [mid + 1, high].
• If arr[mid] is greater than the target, the target must be to the left, so the window shrinks to [low, mid - 1].

Every comparison eliminates roughly half of the remaining candidates, which is why binary search runs in O(log n) time. Going from n elements down to a single remaining element by repeatedly halving takes about log base 2 of n steps: a sorted array of 1,000,000 elements needs at most 20 comparisons, and one of 1,000,000,000 elements needs at most 30. Compare that to linear search, which is O(n) and could need up to a billion comparisons in the worst case on the same data.

Internally, the iterative version of binary search uses only a fixed, small amount of extra memory — three int variables (low, high, mid) no matter how large the array is — so its space complexity is O(1). A recursive version instead pushes one stack frame per halving step, giving it O(log n) stack space; still tiny, but not free, and a compiler may or may not optimize the tail call away. The array itself is never copied or modified — binary search only reads elements and performs index arithmetic, so it works equally well on arrays of integers, floating-point numbers, strings, or structs, as long as you can decide ‘less than’, ‘equal to’, or ‘greater than’ between two elements. This same halving idea extends beyond simple array lookups too: competitive programmers use a technique called ‘binary search on the answer’ to solve optimization problems, and the C standard library itself relies on comparison-based halving inside functions like bsearch(), which you will see in Example 3.

Syntax

The general shape of an iterative binary search function in C looks like this:

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

Each part of the function plays a specific role:

Part	Purpose
low, high	Indices marking the current search window; start at 0 and n - 1.
while (low <= high)	Keeps searching as long as the window still contains at least one element.
mid = low + (high - low) / 2	Computes the middle index without risking integer overflow.
return mid;	Target found — report its index.
low = mid + 1; / high = mid - 1;	Shrinks the window based on the comparison result.
return -1;	Sentinel value meaning ‘not found’, returned once the window becomes empty.

Examples

Example 1: Iterative Binary Search

#include <stdio.h>

int binarySearch(const int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main(void) {
    int numbers[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
    int size = sizeof(numbers) / sizeof(numbers[0]);

    int targets[] = {23, 2, 91, 100};
    int numTargets = sizeof(targets) / sizeof(targets[0]);

    for (int i = 0; i < numTargets; i++) {
        int result = binarySearch(numbers, size, targets[i]);
        if (result != -1) {
            printf("Found %d at index %d\n", targets[i], result);
        } else {
            printf("%d not found in the array\n", targets[i]);
        }
    }

    return 0;
}

Output:

Found 23 at index 5
Found 2 at index 0
Found 91 at index 10
100 not found in the array

This program searches the sorted array numbers for four different targets. For 23, the very first midpoint (index 5) already holds the answer. For 2, the window shrinks twice before landing on index 0. For 91, the window keeps moving right until it lands on the last index, 10. For 100, which does not exist in the array, low eventually becomes greater than high, the loop exits, and the function returns -1 — the conventional sentinel value for ‘not found’ when a function returns a plain int.

Example 2: Recursive Binary Search with a Step Counter

#include <stdio.h>

int binarySearchRecursive(const int arr[], int low, int high, int target, int *steps) {
    if (low > high) {
        return -1;
    }

    (*steps)++;
    int mid = low + (high - low) / 2;

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, high, target, steps);
    } else {
        return binarySearchRecursive(arr, low, mid - 1, target, steps);
    }
}

int main(void) {
    int data[] = {1, 3, 4, 7, 9, 11, 14, 18, 22, 27, 33, 40, 48, 55, 63, 71};
    int n = sizeof(data) / sizeof(data[0]);

    int target = 48;
    int steps = 0;
    int index = binarySearchRecursive(data, 0, n - 1, target, &steps);

    if (index != -1) {
        printf("Value %d found at index %d (checked %d element(s))\n", target, index, steps);
    } else {
        printf("Value %d not found (checked %d element(s))\n", target, steps);
    }

    return 0;
}

Output:

Value 48 found at index 12 (checked 4 element(s))

This version expresses the same algorithm recursively: each call handles one [low, high] window and either returns immediately or calls itself on a window half the size. The steps counter, passed by pointer so every recursive call can update the same variable, tallies how many comparisons were needed. Searching for 48 in a 16-element array takes exactly 4 steps — matching log base 2 of 16 — a concrete way to see the O(log n) bound in action. Notice the base case, if (low > high) return -1;, which stops the recursion once the window becomes empty; forgetting a base case like this is the classic way to turn a recursive function into an infinite chain of calls that eventually crashes with a stack overflow.

Example 3: Using the Standard Library bsearch() Function

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;
    const char *name;
} Product;

int compareById(const void *a, const void *b) {
    const Product *productA = (const Product *)a;
    const Product *productB = (const Product *)b;
    return productA->id - productB->id;
}

int main(void) {
    Product catalog[] = {
        {101, "Keyboard"},
        {105, "Mouse"},
        {110, "Monitor"},
        {118, "Webcam"},
        {124, "Headset"},
        {130, "Speaker"}
    };
    size_t count = sizeof(catalog) / sizeof(catalog[0]);

    Product key = {118, NULL};
    Product *found = bsearch(&key, catalog, count, sizeof(Product), compareById);

    if (found != NULL) {
        printf("Product %d: %s\n", found->id, found->name);
    } else {
        printf("Product %d not found\n", key.id);
    }

    return 0;
}

Output:

Product 118: Webcam

C’s standard library already ships a generic binary search, bsearch(), declared in <stdlib.h>. Instead of hardcoding comparisons for int, it works on an array of any type by taking a pointer to the array, the element count, the size of each element in bytes, and a comparator function you supply. The comparator receives two const void * pointers, casts them back to the real type, and returns a negative, zero, or positive number depending on their order — the same three-way logic binary search always needs. This example searches an array of Product structs sorted by id and finds the one with id == 118 in a handful of comparisons instead of scanning the whole catalog. Using bsearch() instead of hand-writing the loop means you get a well-tested implementation for free, and the same comparator can be reused with qsort() to keep the array sorted in the first place.

How It Works Step by Step (Under the Hood)

To see the halving in action, trace what happens when Example 1’s array is searched for the value 72 (index 9), starting with low = 0 and high = 10:

Step	low	high	mid	arr[mid]	Comparison	Result
1	0	10	5	23	23 < 72	search right half; low = 6
2	6	10	8	56	56 < 72	search right half; low = 9
3	9	10	9	72	72 == 72	found — return 9

Three comparisons were enough to find the element instead of scanning up to ten. Each row shows the window shrinking: 11 candidates, then 5, then 2, then a match — that halving pattern is the entire algorithm.

Common Mistakes

Mistake 1: Running Binary Search on Unsorted Data

Binary search assumes the array is sorted and uses that assumption to decide which half to discard. If the data isn’t actually sorted, the comparison at mid tells you nothing reliable about where the target might be, and the algorithm can walk right past a value that is sitting in the array in plain sight:

#include <stdio.h>

int binarySearch(const int arr[], int size, int target) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main(void) {
    int unsorted[] = {45, 12, 8, 91, 3, 56};
    int size = sizeof(unsorted) / sizeof(unsorted[0]);
    int target = 91;

    int result = binarySearch(unsorted, size, target);
    if (result != -1) {
        printf("Found %d at index %d\n", target, result);
    } else {
        printf("%d not found (but it IS in the array at index 3)\n", target);
    }

    return 0;
}

Output:

91 not found (but it IS in the array at index 3)

Here 91 is clearly present at index 3, but because unsorted isn’t sorted, the search logic discards the wrong half at least once and never looks at index 3 again. The fix isn’t a change to the binary search function itself — it’s making sure the array is sorted first, for example with qsort(), before ever calling binary search on it.

Mistake 2: Computing the Midpoint as (low + high) / 2

A very common way to write the midpoint calculation is mid = (low + high) / 2;. For small arrays this works fine, but if low and high are both large — close to INT_MAX — their sum can overflow a 32-bit int, wrapping to a negative number and producing an out-of-bounds index. The safer formula, mid = low + (high - low) / 2;, gives the same result for ordinary array sizes but never adds two large indices together, so it cannot overflow the same way:

int low = 0, high = 10;
int mid1 = (low + high) / 2;
int mid2 = low + (high - low) / 2;
printf("mid1=%d mid2=%d\n", mid1, mid2);

Output:

mid1=5 mid2=5

Both formulas give the same midpoint here because the indices are small, but only the second one stays safe as array sizes grow into the hundreds of millions.

Mistake 3: Off-by-One Errors That Cause Infinite Loops

It’s easy to update the window boundaries incorrectly and end up with a loop that never terminates. For example, writing high = mid; instead of high = mid - 1; in the ‘search left half’ branch means that when mid itself becomes the new high, the window can stop shrinking and the loop spins forever. The safe pattern is always to exclude mid from the next window on both sides — low = mid + 1 and high = mid - 1 — since mid has already been checked and ruled out.

Best Practices

• Always sort the array first (for example with qsort()); binary search cannot fix unsorted input, it will just silently return wrong or missing results.
• Compute the midpoint as low + (high - low) / 2 rather than (low + high) / 2 to avoid integer overflow on very large index ranges.
• Prefer the iterative version in performance-critical code — it uses constant O(1) stack space, while the recursive version uses O(log n) stack frames.
• When searching arrays of structs, write one comparator function and reuse it for both qsort() and bsearch() so the two never disagree about ordering.
• Avoid comparators that subtract values directly (like a - b) when the values could be very large or negative, since the subtraction itself can overflow; use explicit comparisons instead.
• Document what your function returns when the target isn’t found — a sentinel like -1, a boolean plus an output parameter, or a null pointer — and be consistent across your codebase.
• For data that changes frequently, weigh the cost of re-sorting against the speed benefit binary search provides; if you’re inserting constantly, a different data structure (such as a balanced tree or hash table) may fit better.

Practice Exercises

• Duplicates: Write a function firstOccurrence(arr, size, target) that returns the index of the first (leftmost) occurrence of target in a sorted array that may contain duplicate values. A plain binary search only guarantees finding some matching index, not necessarily the first one.
• Insertion point: Modify Example 1’s binarySearch function so that, when the target isn’t found, it also reports (through an output parameter) the index where the target should be inserted to keep the array sorted.
• Floating-point search: Adapt Example 3’s approach to search a sorted array of double values for a target within a small tolerance (for example, plus or minus 0.0001) instead of exact equality, and explain why exact equality is unreliable for floating-point comparisons.

Summary

• Binary search finds a value in a sorted array in O(log n) time by repeatedly halving the search window.
• It requires sorted data — running it on unsorted data produces silently wrong results.
• Compute the midpoint as low + (high - low) / 2, not (low + high) / 2, to avoid overflow.
• The iterative version uses O(1) extra space; the recursive version uses O(log n) stack space.
• C’s standard library provides a ready-made, generic implementation: bsearch() in <stdlib.h>.
• Keep the comparator used for sorting and the comparator used for searching consistent with each other.