Binary Search: Algorithm and Complexity

In our previous lesson, we implemented linear search and analyzed its O(n) time complexity, noting that it works on any array, sorted or not. This raises a crucial question: if we have the guarantee that an array is sorted, can we devise a search method that is significantly faster than checking every single element?

This lesson answers that with a firm "yes." We will explore binary search, a powerful and highly efficient algorithm for searching in sorted arrays. You will learn its core "divide and conquer" strategy, implement it in C, and understand why its logarithmic time complexity makes it a cornerstone of efficient programming.

1. The "Divide and Conquer" Strategy

Imagine looking for a name in a phone book. You wouldn't start at the first page and read every name until you find the one you're looking for. Instead, you'd open the book somewhere in the middle. If the names on that page come alphabetically after your target, you know you only need to search the first half of the book. If they come before, you search the second half. You repeat this process, halving the search area each time, until you quickly zero in on the right page.

This is the exact logic behind binary search. It works by:

1. Identifying the start (low), end (high), and middle (mid) of the current search area.
2. Comparing the target value to the element at the middle index.
3. If the target matches the middle element, the search is over.
4. If the target is smaller than the middle element, we discard the entire right half of the search area.
5. If the target is larger than the middle element, we discard the entire left half.
6. Repeating this process on the remaining, smaller search area until the value is found or the search area becomes empty.

To see this powerful idea in action, let's watch a short animation.

As the video shows, for binary search to work, two conditions are essential:

• The array must be sorted.
• We need random access to elements (the ability to jump to any index in constant time), which is a natural feature of arrays in C.

2. The Power of Logarithmic Time: O(log n)

In the previous lesson, we learned that the worst-case for linear search is O(n), meaning for an array of 1 million items, we might need 1 million comparisons. How does binary search compare?

Each step in binary search cuts the number of elements to check in half. This "halving" process is incredibly powerful.

Let's watch the next segment of the video, which quantifies this efficiency.

As the video memorably explains, searching for an item in a sorted array of 1 million elements with binary search will take at most 20 steps in the worst case! This is the power of logarithmic growth.

The time complexity of binary search is O(log n) (read as "Order log n"). This is because if you have $n$ elements, the number of times you can halve the set before you're left with just one element is approximately ${\log }_{2}n$.

Let's put this into perspective:

For any large-scale application, the difference is astronomical. This is why understanding and using binary search is so critical.

3. Implementing Binary Search in C

Now, let's translate this algorithm into C code. We will use an iterative approach, which relies on a while loop to manage the search space.

We need three variables to keep track of our search boundaries:

• low: The starting index of the current search space.
• high: The ending index of the current search space.
• mid: The middle index, calculated in each iteration.

The loop continues as long as our search space is valid (low <= high). Inside the loop, we calculate mid, compare arr[mid] with our target, and then update either low or high to shrink the search space for the next iteration.

The following video provides an excellent walkthrough of creating a C function for binary search.

The video highlighted a subtle but important detail for calculating the middle index:

This is preferred over the more direct (low + high) / 2 because for extremely large arrays, low + high could overflow the maximum value an int can store. This version avoids that risk.

For a textual reference, the following article provides a clean, commented implementation.

4. Practice: Your Binary Search Program

It's time to put theory into practice. Below is a complete C program that implements and tests the binarySearch function. Your task is to compile, run, and experiment with it.

#include <stdio.h>

// Function to perform iterative binary search on a sorted array
// arr: the sorted array to search in
// size: the number of elements in the array
// target: the value to search for
// Returns the index of the target if found, otherwise returns -1
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    // Loop until the search space is empty (low > high)
    while (low <= high) {
        // Calculate mid-point to avoid potential overflow
        int mid = low + (high - low) / 2;

        // Check if target is present at mid
        if (arr[mid] == target) {
            return mid; // Target found
        }

        // If target is greater, ignore the left half
        if (arr[mid] < target) {
            low = mid + 1;
        } 
        // If target is smaller, ignore the right half
        else {
            high = mid - 1;
        }
    }

    // If we reach here, the element was not present
    return -1;
}

int main() {
    // Binary search requires a SORTED array
    int numbers[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    
    int target1 = 23;
    int target2 = 7; // A value not in the array

    // --- Test Case 1: Element is in the array ---
    int result1 = binarySearch(numbers, size, target1);

    if (result1 != -1) {
        printf("Target %d found at index: %d\n", target1, result1);
    } else {
        printf("Target %d was not found in the array.\n", target1);
    }

    // --- Test Case 2: Element is NOT in the array ---
    int result2 = binarySearch(numbers, size, target2);

    if (result2 != -1) {
        printf("Target %d found at index: %d\n", target2, result2);
    } else {
        printf("Target %d was not found in the array.\n", target2);
    }

    return 0;
}

Your Task:

1. Copy, compile, and run this code in your development environment.
2. Verify the output: 23 should be found at index 5, and 7 should not be found.
3. Modify the main function to search for the first element (2) and the last element (91). Observe how the algorithm finds them.
4. Challenge Question: What do you think would happen if you tried to run binarySearch on an unsorted array like {56, 12, 91, 2, 38}? Explain why the algorithm would fail to produce a correct result.

Conclusion

In this lesson, you have added a powerful and efficient algorithm to your toolkit. By leveraging the "divide and conquer" method on sorted data, binary search provides a dramatic performance improvement over linear search.

Key Takeaways:

• Binary search operates on sorted arrays by repeatedly dividing the search interval in half.
• Its time complexity is O(log n), making it exceptionally fast for large datasets.
• The iterative implementation uses a while loop with low and high pointers to manage the search space.
• The iterative approach has a space complexity of O(1), as it uses a constant amount of extra memory.
• A key prerequisite is a sorted collection with random access.

Preview of the Next Lesson:
The immense efficiency of binary search underscores the value of having sorted data. But how do we get our data into a sorted order in the first place? In the next lesson, we will begin our journey into sorting algorithms, starting with one of the most straightforward and intuitive methods: bubble sort.