Binary Search in C: Complete Guide with Code

Searching algorithms are a fundamental part of computer science, and binary search is one of the most efficient techniques for locating an element in a sorted array. In this blog, you’ll learn how binary search works in C, understand its core logic, and see it in action with real code examples.

What is Binary Search?

Binary search is a searching algorithm used on sorted arrays. Instead of checking each element sequentially, it repeatedly divides the search range in half, reducing the number of comparisons significantly.

Key Features:

Works only with sorted arrays
Time complexity: O(log n)
Space complexity: O(1) for iterative version

How Binary Search Works

Here’s the basic logic behind binary search:

Start by identifying the middle element of the array.
If this element matches the target, return its index.
If the target is smaller, repeat the search on the left half.
If the target is larger, repeat the search on the right half.
Continue this process until the element is found or the range is exhausted.

Binary Search in C: Iterative Approach

Below is a simple C program demonstrating binary search using an iterative method.

#include <stdio.h>

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

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

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1; // Element not found
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 7;

    int result = binarySearch(arr, size, target);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");

    return 0;
}

Recursive Binary Search in C

The binary search algorithm can also be implemented recursively.

int binarySearchRecursive(int arr[], int low, int high, int target) {
    if (low > high)
        return -1;

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

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return binarySearchRecursive(arr, low, mid - 1, target);
    else
        return binarySearchRecursive(arr, mid + 1, high, target);
}

Iterative vs Recursive Binary Search

Feature	Iterative	Recursive
Time Complexity	O(log n)	O(log n)
Space Complexity	O(1)	O(log n) (due to stack)
Use Case	Preferred for performance	Preferred for readability

Common Mistakes to Avoid

Applying binary search to unsorted arrays
Using mid = (low + high)/2 without checking for overflow
Forgetting to correctly update low or high

Applications of Binary Search

Binary search is widely used in various domains:

Searching in databases and large datasets
Optimizing file systems and libraries
Solving algorithmic problems in competitive programming
Powering search functionalities in software and web applications

Tips to Practice

To strengthen your understanding of binary search:

Try modifying the algorithm to find the first or last occurrence of a target
Implement binary search on rotated sorted arrays
Explore variations like order-agnostic binary search

Conclusion

Binary search is a must-know algorithm for every programmer. It provides an elegant and efficient solution for searching problems, especially when working with sorted data. By mastering binary search in C, you not only improve your problem-solving skills but also prepare yourself for coding interviews and real-world challenges.

Learn More and Get Placed

Our Placement Guaranteed Course Program, designed by top IITians and senior developers, ensures job placement with a CTC of up to 25 LPA. Get expert guidance, hands-on coding practice, and interview prep tailored for top tech companies like Visa. 👉 Learn More & Secure Your Dream Job!

Recent Posts