Binary Search in C: Re-running Our 2021 Code

Revised November 2026. This tutorial first appeared in Korean in 2021. When we re-ran it, the example no longer compiled with a current C compiler, the comparison counts in the text were off by one, and the midpoint calculation had an overflow bug. Everything below was re-measured on an Apple M1 Pro with Apple clang 21.

The idea

Binary search finds a value in a sorted array by comparing it with the middle element and discarding the half that cannot contain it. Each comparison halves the search range, which is where the name comes from.

To get a feel for the speed: finding one item among 7 billion takes a linear search 3.5 billion comparisons on average. Binary search needs at most 33, and we verify that number below.

Walking through an example

Let's find 8 in the sorted array above. First, pick the middle element.

Compare it with the target. If the target is smaller, continue in the left half; if larger, in the right half. 8 is larger than the middle value 7, so the whole left half is skipped and we pick the middle of the right half.

The middle is now 9. 8 is smaller, so we continue to the left.

The remaining element, 8, becomes the middle and matches the target, so the search ends.

How many comparisons (a correction)

Each comparison halves the range. With n elements and k steps, k is how many times n can be halved before reaching 1, so k ≈ log2(n).

The original article said "at most 22 comparisons for 5 million elements and 23 for 10 million". Both were one too low. The worst case is floor(log2 n) + 1. We counted it directly:

/* Count iterations in the worst case: searching for the last element */
static long worst_iters(long long n) {
    long long lo = 0, hi = n - 1; long it = 0;
    while (lo <= hi) {
        it++;
        long long mid = lo + (hi - lo) / 2;
        if (mid < n - 1) lo = mid + 1; else return it;
    }
    return it;
}

The implementation (fixed)

int BinarySearch(const int dataArr[], int size, int findData)
{
    int low = 0, high = size - 1;
    while (low <= high)                      /* empty range: not found */
    {
        int mid = low + (high - low) / 2;    /* (low + high) / 2 overflows, see below */
        if (dataArr[mid] > findData)      high = mid - 1;
        else if (dataArr[mid] < findData) low = mid + 1;
        else return mid;                     /* found */
    }
    return -1;
}

low and high are the left and right ends of the current range, and mid is its middle. Two things changed from the 2021 version.

1. mid = (low + high) / 2 breaks on large arrays

If low + high exceeds the largest int (2,147,483,647), the sum overflows. With arrays of more than about a billion elements this really happens:

overflow: low+high=3500000000 > INT_MAX=2147483647
          (int)(low+high)/2  = -397483648      <- negative index
          low+(high-low)/2   = 1750000000      <- correct

low + (high - low) / 2 is mathematically the same value, but no intermediate result leaves the range. This bug is common enough that it sat in Java's standard library binary search for years.

2. The example did not compile as written

The 2021 main used while (true). In C, true needs <stdbool.h> (it only became a keyword in C23):

$ cc -std=c17 orig.c
orig.c:27:12: error: use of undeclared identifier 'true'
   27 |     while (true) {

It also never checked scanf's return value. When input ended, the loop kept printing the result for the last value forever. The fixed example:

Example (fixed)

#include <stdio.h>

int BinarySearch(const int dataArr[], int size, int findData);   /* as above */

int main(void)
{
    int dataArr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 21, 24, 26, 27, 28};
    int length = sizeof dataArr / sizeof dataArr[0];
    int input;

    while (scanf("%d", &input) == 1) {       /* stop at end of input */
        int ret = BinarySearch(dataArr, length, input);
        if (ret != -1) printf("Found at position %d.\n", ret + 1);
        else           printf("Not found.\n");
    }
    return 0;
}

$ printf "28\n4\n7\n17\n99\n" | ./bs
Found at position 21.
Found at position 4.
Found at position 7.
Found at position 16.
Not found.

It compiles cleanly with -std=c17 -Wall -Wextra and exits when the input ends.

Measured against linear search

We looked up 1,000 random values in a sorted array of 10 million ints (a[i] = i * 2), built with clang -O2:

That is roughly 18,000 times faster. The catch is the precondition: the data must be sorted. If you search only once, the sort (O(n log n)) costs more than a linear scan. Binary search pays off when you search the same data many times.

In real code

• C has bsearch() in the standard library; you pass a comparison function.
• If the array contains duplicates and you need the first occurrence, keep narrowing to the left after a match (a lower-bound search). The version above returns any matching position.
• C++ has std::lower_bound and std::binary_search, Python has the bisect module, and C# has Array.BinarySearch. Writing it yourself is for learning; in production, use the library.