Binary Search in C: Algorithm, Boundary Checks & Interactive Practice

Binary search challenge workbench isolating a target key in O(log n) steps.
Binary search challenge workbench isolating a target key in O(log n) steps.

Problem Statement

Implement the Binary Search algorithm in C on a sorted array of N integers. Given a target value K, return the 0-based index of K in the array. If K is not present, return -1.

Real-World Systems Context

Binary search is the backbone of database indexing (B-Trees), symbol table lookups in compilers, and binary package management. When datasets grow to millions of records, linear search crawls to a halt, while binary search finds the target in fewer than 25 steps.

Requirements:

  1. Read N (array size) and target K from standard input.
  2. Read N sorted integers.
  3. Implement int binary_search(int arr[], int n, int target) using the divide-and-conquer strategy.
  4. Avoid integer overflow in midpoint calculation: use mid = low + (high - low) / 2 instead of (low + high) / 2.
  5. Print Found at index: <index> or Not found: -1.

Complexity & Editorial

Why Binary Search Delivers Logarithmic O(log N) Performance

Linear search checks elements one by one, requiring O(N) comparisons in the worst case. Searching a sorted array with 1,000,000 elements linearly can take 1,000,000 operations.

Binary search exploits the sorted order by comparing the target with the middle element:
• If target == arr[mid], the element is found immediately.
• If target < arr[mid], all elements to the right of mid are guaranteed to be larger than target, so we narrow our search interval to the left half: high = mid - 1.
• If target > arr[mid], all elements to the left are smaller, so we search the right half: low = mid + 1.

Because each comparison cuts the remaining search space strictly in half, the maximum number of steps required is log2(N). For 1,000,000 elements, binary search finds the answer in at most 20 iterations!

The Famous Midpoint Integer Overflow Bug

For decades, textbooks wrote int mid = (low + high) / 2. In 2006, Joshua Bloch pointed out that when low + high exceeds INT_MAX (2,147,483,647), the sum wraps around to a negative number, resulting in an array out-of-bounds crash. Writing mid = low + (high - low) / 2 is mathematically identical but completely eliminates arithmetic overflow.

Starter Code

#include <stdio.h>

// Function to perform binary search
// Returns 0-based index of target if found, else -1
int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

    // TODO: Implement O(log N) binary search loop
    // Tip: Use mid = low + (high - low) / 2 to prevent integer overflow

    return -1; // Target not found
}

int main(void) {
    int n, target;
    if (scanf("%d %d", &n, &target) != 2 || n <= 0) {
        return 1;
    }

    int arr[100];
    for (int i = 0; i < n && i < 100; i++) {
        scanf("%d", &arr[i]);
    }

    int result = binary_search(arr, n, target);
    if (result != -1) {
        printf("Found at index: %d\n", result);
    } else {
        printf("Not found: -1\n");
    }

    return 0;
}

Frequently Asked Questions

Why does binary search require a sorted array?

Binary search relies on the invariant that elements to the left of any index are smaller and elements to the right are larger. If the array is unsorted, discarding half the array could inadvertently discard the target element.

Can binary search be implemented recursively?

Yes, but iterative binary search is preferred in production C because it runs in O(1) space, avoiding function call overhead and call stack consumption.

Related exercises