Imagine we're building a system to manage a massive database of User IDs—let's say about a million of them—all stored in a sorted array. If you need to check if a specific ID exists in that list, your first instinct might be to just start at the beginning and check every single one until you find a match. It's simple, it's intuitive, and it's exactly how we'd look for a name in a list if we didn't know the list was alphabetical.

The cost of checking every door

This "naive" approach is what we call a linear search. In C, it looks like a basic for loop. The problem is that linear search has a time complexity of O(n). If the User ID you're looking for is at the very end of that million-element array, your CPU has to perform a million comparisons. While a modern processor handles a million operations quickly, this becomes a massive bottleneck when you're doing thousands of lookups per second or working with datasets that grow into the billions. I've seen production systems crawl to a halt simply because someone used a linear search inside another loop, accidentally creating an O(n²) nightmare.

Cutting the search space in half

Since we know our array is already sorted, we can be much smarter. Instead of checking one by one, we jump straight to the middle. If the ID at the midpoint is larger than the one we want, we know our target must be in the left half. We can throw away the entire right half of the array in a single operation. We repeat this—splitting the remaining search area in half over and over—until we either find the ID or run out of elements to check.

This is binary search. It turns an O(n) problem into an O(log n) problem. To put that in perspective: for a million elements, a linear search might take 1,000,000 steps, but a binary search will take at most 20. That's not just a slight improvement; it's a fundamental shift in performance.

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

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

        if (arr[mid] == target) {
            return mid; // Found it!
        }
        if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // Not found
}

The integer overflow trap

You'll see a lot of textbooks and old Stack Overflow posts tell you to calculate the midpoint using mid = (low + high) / 2;. In a classroom setting, that works fine. In the real world, it's a bug waiting to happen. If low and high are both very large positive integers, adding them together can exceed the maximum value an int can hold. This causes an integer overflow, resulting in a negative number, which then leads to a segmentation fault when you try to use it as an array index.

I used mid = low + (high - low) / 2; in the code above. It's mathematically identical to the naive version, but it avoids the overflow because it subtracts before it adds. It's a small detail, but it's the kind of thing that separates a junior implementation from professional-grade code. When you're dealing with memory and raw pointers in C, these "edge cases" are where most of your bugs will live.

📋 Practical Task

Exercise: Implementing a Sorted Temperature Log Lookup

You are working on a firmware project for a weather station. The station stores hourly temperature readings for a full year (8,760 readings) in a sorted array called temp_log. Your task is to implement a function int find_reading_index(int temp_log[], int size, int target_temp) that uses binary search to find the index of a specific temperature value.

Requirements:

• The function must return the index of the target_temp if it exists in the array.
• If the temperature is not found, return -1.
• You must implement the midpoint calculation in a way that prevents integer overflow.
• Test your function with a sorted array of at least 100 elements to ensure the logic handles the boundaries (first element, last element, and missing elements) correctly.