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

Worked example

Searching for 11 in the sorted array {2, 3, 7, 7, 11, 15, 25} (indices 0-6):

  • lo=0, hi=6: mid=3, arr[3]=7. 7 < 11, so lo becomes 4.
  • lo=4, hi=6: mid=5, arr[5]=15. 15 > 11, so hi becomes 4.
  • lo=4, hi=4: mid=4, arr[4]=11. Match — return index 4.

Three comparisons instead of a seven-step linear scan. Trace this by hand before typing the loop — it confirms the invariant that the target, if present, always lies within [lo, hi], which is exactly where off-by-one bugs hide in C's pointer/index 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

  • Best case: O(1) — the target is at the first mid index checked
  • Average case: O(log n)
  • Worst case: O(log n)
  • Space: O(1) iterative, O(log n) recursive (call stack)