LiveCodingInterview.com
← Articles

How to Implement Binary Search in C

C binary search appears in systems interviews, embedded roles, and any loop where you need explicit control over memory and indices. The logic is the same as other languages — only syntax and pointer habits differ.

For the conceptual guide (two methods, jump search, interview variants), see Binary Search Algorithm: A Coding Interview Guide.

Prerequisites

  • Sorted array of integers (ascending)
  • Array length `n` passed explicitly or known from context
  • **O(log n)** time, **O(1)** space for iterative code
int binary_search(const int *arr, int n, int x) {
    int lo = 0;
    int hi = n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }

    return -1;
}

Use `const int *arr` when the function does not modify the array. Always compute `mid` as `lo + (hi - lo) / 2` to avoid integer overflow.

Recursive version

int binary_search_rec(const int *arr, int x, int lo, int hi) {
    if (lo > hi) return -1;

    int mid = lo + (hi - lo) / 2;

    if (arr[mid] == x) return mid;
    if (arr[mid] > x) return binary_search_rec(arr, x, lo, mid - 1);
    return binary_search_rec(arr, x, mid + 1, hi);
}

// Call: binary_search_rec(arr, x, 0, n - 1);

Complete example with main

#include <stdio.h>

int binary_search(const int *arr, int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) hi = mid - 1;
        else lo = mid + 1;
    }
    return -1;
}

int main(void) {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", binary_search(arr, n, 5)); // 2
    return 0;
}

C-specific pitfalls

  • **No built-in length** — pass `n` or track size with `sizeof` for static arrays only
  • **Unsigned pitfalls** — keep `lo` and `hi` as `int`; mixing unsigned types breaks `hi = mid - 1` when `mid` is 0
  • **Do not pointer-arithmetic past bounds** — indices only
  • Empty array: if `n == 0`, return `-1` before the loop

bsearch from stdlib

C provides `bsearch` in `<stdlib.h>`. It requires a comparator function and is less common in interviews:

#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(const int *)a - *(const int *)b;
}

// int *found = bsearch(&key, arr, n, sizeof(int), compare);

Prefer writing the loop by hand in interviews.

Complexity

  • **Time:** O(log n)
  • **Space:** O(1) iterative