Binary Search Using Recursion in C

Binary Search algorithm

Binary search is one of the most efficient algorithms for searching a value in a sorted array. Unlike linear search, which traverses each element sequentially, binary search repeatedly divides the search space in half, making it much faster with a time complexity of O(log n). In this article, we’ll explore how to implement binary search using recursion in the C programming language.

What is Binary Search?

Binary search works on the divide-and-conquer principle. It splits the array into two halves, compares the target element with the middle element, and decides which half of the array to search next. The process continues recursively until the element is found or the search space is empty.

Key Points:

• Works only on sorted arrays: Binary search requires the array to be sorted in ascending or descending order.
• Faster than linear search: For an array of size n, binary search requires at most log2(n) comparisons.

Recursive Approach to Binary Search

The recursive method involves repeatedly calling the same function with updated start and end indices. Let’s look at the steps:

1. Calculate the middle index of the array.
2. Compare the middle element with the target:

• If they match, return the index.
• If the target is smaller, search in the left half.
• If the target is larger, search in the right half.

3. Repeat the process until the target is found or the search space becomes invalid.

Code Implementation in C

Below is a recursive implementation of binary search in C:

#include <stdio.h>

// Recursive function for binary search
int binarySearch(int arr[], int start, int end, int target) {
    if (start <= end) {
        int mid = start + (end - start) / 2;
        // Check if the middle element is the target
        if (arr[mid] == target) {
            return mid;
        }
        // If target is smaller, search the left half
        if (arr[mid] > target) {
            return binarySearch(arr, start, mid - 1, target);
        }
        // If target is larger, search the right half
        return binarySearch(arr, mid + 1, end, target);
    }
    // Return -1 if the target is not found
    return -1;
}
int main() {
    int array[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int n = sizeof(array) / sizeof(array[0]);
    int target = 14;
    // Call the binary search function
    int result = binarySearch(array, 0, n - 1, target);
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found in the array.\n");
    }
    return 0;
}

Example Walkthrough

Let’s break down the execution of the above code for the target value 14:

1. Initial call: Start = 0, End = 9, Middle = 4. Array[4] = 10.

• 14 > 10, so search in the right half (Start = 5, End = 9).

2. Second call: Start = 5, End = 9, Middle = 7. Array[7] = 16.

• 14 < 16, so search in the left half (Start = 5, End = 6).

3. Third call: Start = 5, End = 6, Middle = 5. Array[5] = 14.

• Target found at index 5.

Advantages of Binary Search

• Efficient: Handles large datasets quickly.
• Deterministic: Guaranteed to find the element or confirm its absence.

Limitations of Binary Search

• Requires sorted data: An unsorted array must be sorted first, which adds extra overhead.
• Complex implementation: Recursive implementations can lead to stack overflow for very large arrays.

When to Use Binary Search

Binary search is best suited for:

• Searching in sorted arrays or lists.
• Scenarios where performance is critical and datasets are large.

Conclusion

Binary search is a foundational algorithm that every programmer should master. The recursive implementation in C is clean and demonstrates the divide-and-conquer approach beautifully. Practice writing and optimizing this code to solidify your understanding. Happy coding!

Binary Search algorithm