What You Will Learn

• How to package binary search as a function that returns an index or -1
• How to count probes to see the speed of the algorithm for yourself
• Why the function takes the array size as a parameter
• How a lower-bound search maps a reading to a range (band) in embedded C programming
• How to test first, last, middle and missing values

Prerequisites

• The previous lecture, where low, high and mid were traced by hand
• Functions with arguments and return values (Functions chapter)
• Passing arrays and pointers to functions, and const parameters
• The uint16_t type from <stdint.h> (we introduce it briefly below)

Designing the Binary Search Function

Before writing code, decide what the function promises to the caller. A good contract keeps the program easy to test.

Part	Decision	Reason
Parameter 1	const int a[]	The search only reads the array, so const protects the data
Parameter 2	int n	An array parameter does not remember its length, so the caller passes it
Parameter 3	int key	The value to look for
Extra output	int *probes	Lets us measure how many elements were inspected
Return value	Index, or -1	-1 can never be a valid array index

Complete Binary Search Program in C

The program below contains two functions and a main that tests five keys. Save it as ep_bsearch.c. It uses a lower-bound function too, which we explain in the next section.

#include <stdio.h>
#include <stdint.h>

#define TABLE_SIZE 10
#define BAND_COUNT 6

/* Returns index of key in a[0..n-1] (sorted ascending) or -1.
   *probes receives the number of elements inspected. */
static int ep_binary_search(const int a[], int n, int key, int *probes)
{
    int low = 0;
    int high = n - 1;

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

        (*probes)++;
        if (a[mid] == key)
            return mid;
        if (key < a[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

/* First index whose element is >= value; n when every element is smaller. */
static int ep_lower_bound(const uint16_t a[], int n, uint16_t value)
{
    int low = 0;
    int high = n;

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

        if (a[mid] < value)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

int main(void)
{
    const int table[TABLE_SIZE] = {3, 8, 14, 21, 27, 35, 42, 56, 63, 71};
    const int keys[5] = {35, 30, 3, 71, 100};
    const uint16_t adc_limit[BAND_COUNT] = {512, 1024, 1536, 2048, 3072, 4095};
    const uint16_t readings[4] = {100, 1000, 2049, 4095};

    for (int k = 0; k < 5; k++) {
        int probes;
        int idx = ep_binary_search(table, TABLE_SIZE, keys[k], &probes);

        if (idx >= 0)
            printf("key %3d: found at index %d after %d probes\n",
                   keys[k], idx, probes);
        else
            printf("key %3d: not found after %d probes\n", keys[k], probes);
    }

    printf("\nADC band lookup\n");
    for (int r = 0; r < 4; r++)
        printf("reading %4u -> band %d\n", (unsigned)readings[r],
               ep_lower_bound(adc_limit, BAND_COUNT, readings[r]));
    return 0;
}

Build and run:

gcc -std=c17 -Wall -Wextra -o ep_bsearch ep_bsearch.c
./ep_bsearch

Expected output:

key  35: found at index 5 after 3 probes
key  30: not found after 3 probes
key   3: found at index 0 after 3 probes
key  71: found at index 9 after 4 probes
key 100: not found after 4 probes

ADC band lookup
reading  100 -> band 0
reading 1000 -> band 1
reading 2049 -> band 4
reading 4095 -> band 5

Reading the Output of the Binary Search Program

The first two lines repeat what you traced in the last lecture: 35 is found at index 5 and 30 is not found, each in three probes. The other keys are the edge cases every test must include.

Key	Why it is tested	Probes	Result
35	A value in the right half of the table	3	index 5
30	Missing value between two stored values	3	-1
3	First element (checks that low = 0 works)	3	index 0
71	Last element (checks that high = n - 1 works)	4	index 9
100	Larger than every element	4	-1

No search needed more than four probes for ten elements, which matches the formula floor(log₂ 10) + 1 = 4. Try changing TABLE_SIZE and the table data to prove to yourself that the probe count grows very slowly.

Lower-Bound Search for Embedded ADC Tables

Sometimes you do not want an exact match. A 12-bit ADC returns any value from 0 to 4095, but your firmware only needs to know which range the reading falls in: for example which temperature band, battery level or key-pad button. The thresholds are stored in a sorted table, and the answer is “the first threshold that is greater than or equal to the reading”.

That is called a lower-bound search. Look at how it differs from the exact search:

• high starts at n, not n - 1, because “no threshold is large enough” is a valid answer (the function then returns n).
• The loop condition is low < high.
• When a[mid] < value we move low = mid + 1; otherwise high = mid, because mid itself might be the answer.

Reading 1000 is larger than 512 but not larger than 1024, so band 1 is returned. Reading 2049 is above 2048, so it lands in band 4. In the output above all four readings agree with this table.

Real-World Uses of Binary Search in C

Application	Sorted table holds	Search type
Thermistor temperature	ADC counts for known temperatures	Lower bound, then interpolate
Key-pad with resistor ladder	ADC thresholds per button	Lower bound
Bootloader command parser	Command IDs	Exact match
CAN message filter	Accepted identifiers	Exact match
Font or glyph lookup in a display driver	Character codes	Exact match

Common Mistakes and Troubleshooting

• Forgetting to pass the size. Inside a function, sizeof(a) gives the size of a pointer, not the array. Always pass n.
• Calling the function on unsorted data. Add a comment or an assertion in debug builds. Results are meaningless otherwise.
• Using unsigned for high. When mid is 0 and the key is smaller, high = mid - 1 wraps around to a huge number. Keep indexes as signed int in the exact-match version.
• Mixing the two loop styles. The exact-match version uses low <= high with high = n - 1. The lower-bound version uses low < high with high = n. Copying one condition into the other causes off-by-one bugs.
• Compiler warnings about unused probes. If you remove the counter after testing, remove the parameter too.

Best Practices, Performance and Security

• Performance: the loop uses only integer additions, one subtraction and a shift-like division by 2. Compilers turn / 2 on a signed value into a few instructions, which is cheap even on small cores.
• Determinism: the worst-case probe count is fixed by the table size, so you can budget CPU cycles for interrupt handlers.
• Security: if the key or table size is influenced by external data, validate it before calling the function and never let n exceed the real array length.
• Testing: keep a small test table with the five cases above in your project and run it whenever the search function changes.
• Standard library: on hosted systems C already provides bsearch() in <stdlib.h>. Writing your own teaches the idea, and bare-metal builds often have no such library.

Summary and Key Takeaways

• Put binary search in a function that returns the index or -1 and takes the size as an argument.
• Test first, last, middle, missing and too-large keys.
• Probe counts stay tiny: four probes were enough for ten elements.
• A lower-bound search answers “which range?” questions and is common in ADC and sensor code.
• Keep indexes signed and compute mid as low + (high - low) / 2.

Conclusion

You have now seen binary search as a complete, tested C program and as a practical tool for embedded firmware. The same discipline, a clear contract and edge-case tests, applies to every algorithm in this free C programming course. Next we start sorting, because binary search is only useful when the array is in order. The first sorting method is selection sort.

Frequently Asked Questions

How do I write a binary search program in C?

Keep low and high indexes, compute mid inside a loop that runs while low is not greater than high, and move low or high past mid depending on the comparison.

What does the function return when the key is missing?

In this lecture it returns -1, because -1 can never be a valid array index.

Should I use recursion for binary search?

The loop version is preferred in embedded C. It uses constant stack space, while recursion adds a stack frame per step.

What is the difference between exact search and lower bound?

Exact search needs a matching value. Lower bound returns the first position whose element is at least the given value, even if no element equals it.

Can I use binary search on a 2-D array?

Only if you treat the data as one sorted sequence, for example one sorted row. Each row must be searched separately otherwise.

Is bsearch() in the C standard library the same thing?

Yes, it implements the same idea with a comparison function, but it is not always available in minimal embedded libraries.