Understanding Binary Search in C: Working, Implementation, and Code Examples

When it comes to efficient searching in large datasets, one algorithm that often stands out is binary search. Especially for C programmers who want speed and performance, binary search in C is an essential tool to have in their coding toolkit. But what makes this algorithm so popular, and how does it actually work, and why every top-rated software development course has this concept. 

In this blog, we’ll dive deep into the world of binary search in C, from understanding the core logic and requirements, to actually writing the code and analyzing its efficiency. Whether you're a beginner learning C or a seasoned developer brushing up on algorithms, you'll find this guide practical and easy to follow.

By the end of this post, you’ll not only know how to implement binary search in C, but also when and why to use it, its pros and cons, and what makes it different from other searching methods. Let’s get started! 

What is Binary Search in C?

Before jumping into the implementation, it’s important to understand what binary search is and why it’s widely used. Additionally, you should also learn about the following concepts: 

• Array in C 
• One dimensional array in C 
• Two dimensional array in C 
• Structure of a C program 

All these concepts will help you build a strong foundation for binary search in C. 

Binary search in C is a search algorithm that operates on sorted arrays. The core idea is to eliminate half of the remaining elements with each comparison. It’s based on the "divide and conquer" strategy, which makes it much more efficient than linear search for large datasets.

Let’s break it down with a quick scenario.

Suppose you have this sorted array:

int arr[] = {3, 10, 17, 25, 31, 44, 59, 68, 72};

If you're looking for the value `31`, binary search in C works like this:

1. Check the middle element (`25`).

2. Since `31 > 25`, you ignore the left half of the array.

3. Now the search continues in the right half: `{31, 44, 59, 68, 72}`.

4. The new middle is `59`. Since `31 < 59`, ignore the right half.

5. Now only `{31}` remains, and the element is found.

This method drastically reduces the number of comparisons. In fact, the time complexity of binary search in C is O(log n), compared to O(n) for linear search.

Now let’s see this in action with actual C code.

Elevate your expertise in software engineering with these leading programs:

•  Master’s in Data Science - LJMU
•  PG Diploma in Machine Learning & AI – IIT Bangalore
• Master of Science in AI & Data Science – Jindal Global University 

C Program: Binary Search in C

#include <stdio.h>

// Function to perform binary search
int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = (low + high) / 2;  // Calculate middle index

        if (arr[mid] == target) {
            return mid;  // Target found
        } else if (arr[mid] < target) {
            low = mid + 1;  // Search right half
        } else {
            high = mid - 1;  // Search left half
        }
    }

    return -1;  // Target not found
}

int main() {
    int arr[] = {3, 10, 17, 25, 31, 44, 59, 68, 72};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 31;

    int result = binarySearch(arr, size, target);

    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }

    return 0;
}

Output:

Element 31 found at index 4.

Explanation:

This program demonstrates how binary search in C efficiently locates a target element in a sorted array:

• The array is sorted in ascending order, which is a strict requirement for binary search.
• The function `binarySearch` calculates the middle index in each iteration.
• It compares the middle element with the target and adjusts the search range accordingly.
• If the target is found, it returns the index.
• If the search range is exhausted, it returns `-1`.

This is a foundational algorithm that combines logical thinking with performance-focused coding. Understanding binary search in C is key to mastering data structures and algorithms in the C programming language.

Also, if-else statement and loops in C are also used for binary search program, and you should also understand these concepts for better understanding. 

Conditions to Apply Binary Search Algorithm in a C Program

Before using binary search in C, it's crucial to understand when it is applicable. The algorithm is not a one-size-fits-all solution. While it's extremely efficient, there are a few conditions that must be satisfied for it to work correctly.

Let’s go over those essential requirements.

1. The Array Must Be Sorted

This is the most important rule. Binary search in C only works on arrays that are sorted in ascending or descending order. If the array is unsorted, the logic of halving the search space breaks down, and the algorithm will not work as intended.

If you have an unsorted array, you need to sort it first using a sorting algorithm like quicksort, mergesort, or even bubblesort for smaller datasets.

// Binary search will not work correctly here
int arr[] = {10, 2, 45, 7, 19};  // Unsorted array

// Correct usage
int sortedArr[] = {2, 7, 10, 19, 45};  // Sorted array

2. Static or Random Access Structure

Binary search in C is typically applied to arrays where you can access elements in constant time using an index. This is known as random access. Arrays, being statically indexed, are perfect for this.

On the other hand, linked lists or other sequential access data structures are not suitable because you can't directly jump to the middle element without traversing the list.

3. Comparable Elements

The elements in the array must be comparable using relational operators (`<`, `>`, `==`, etc.). This means binary search works well with integers, floats, characters, and other primitive data types.

If you're using complex structures (like structs), you’ll need to define a comparison logic before applying binary search in C. Also explore out article on conditional operators in C to gain deep insights on operators. 

4. Defined Bounds

Binary search operates within a known range, typically between the lowest and highest indices of the array. In your function, this means maintaining `low` and `high` pointers to define the current search interval.

Without well-defined bounds, the algorithm can’t accurately zero in on the target value.

Furthermore, to recap, here are the four key conditions to apply binary search in C:

• The array must be sorted.
• The data structure in C should allow constant-time access (like arrays).
• Elements must be comparable using standard operators.
• Search bounds (`low` and `high`) should be clearly defined.

Skipping any of these can lead to incorrect results, infinite loops, or program crashes. Following these conditions ensures that binary search in C runs safely, efficiently, and as expected.

Algorithm for Binary Search in C: Pseudo Code & Working

Understanding the logic behind binary search is essential before jumping into actual code. Many bugs in search algorithms stem from misunderstandings of how boundaries (`low` and `high`) shift, or how the middle index is calculated.

In this section, we’ll walk through a clear, step-by-step breakdown of how binary search in C works, what decisions the algorithm makes, and why it’s so efficient. We’ll also discuss pseudo code as a precursor to writing clean C code.

How Binary Search Works – A Detailed Breakdown

Let’s start with a sorted array:

int arr[] = {5, 12, 18, 23, 35, 47, 59, 63, 70};

Let’s say we want to find the value `35`. Here's how binary search in C would approach it:

Initial Setup:

• `low = 0`
• `high = 8` (since array size is 9)
• Calculate `mid = (low + high) / 2 = 4`
• Check `arr[mid]` → `arr[4] = 35`

Target found in the first step! But that’s not always the case. Let’s try finding `18` instead.

Tracing the Search for 18:

Step 1:

• `low = 0`, `high = 8`
• `mid = (0 + 8) / 2 = 4` → `arr[4] = 35`
• Since `18 < 35`, search the left half
• Update: `high = mid - 1 = 3`

Step 2:

• `low = 0`, `high = 3`
• `mid = (0 + 3) / 2 = 1` → `arr[1] = 12`
• Since `18 > 12`, search the right half
• Update: `low = mid + 1 = 2`

Step 3:

• `low = 2`, `high = 3`
• `mid = (2 + 3) / 2 = 2` → `arr[2] = 18`

Target found!

We found `18` in just 3 comparisons instead of scanning all 9 elements. That’s the power of binary search in C—each iteration cuts the search space in half.

Pseudo Code for Binary Search in C

Writing pseudo code in C helps you understand the algorithm independently of programming language syntax. Here’s a clean, readable version tailored for implementation in C:

Function binarySearch(array, target):

   low ← 0
    high ← length(array) - 1

    While low ≤ high:
        mid ← (low + high) / 2

        If array[mid] == target:
            Return mid

        Else If array[mid] < target:
            low ← mid + 1

        Else:
            high ← mid - 1

    Return -1  // Target not found

This pseudo code maps almost one-to-one with C syntax, which makes it ideal for translating into a working C function.

Why This Works So Well

Each time we don’t find the target, we discard half of the remaining search space. This results in a time complexity of:

• Best case: O(1) — target is at the middle
• Worst case: O(log n) — repeatedly halving the array
• Average case: O(log n)

This logarithmic growth is what makes binary search in C ideal for large sorted arrays. For example, in an array of 1,000,000 elements, it will take at most 20 comparisons to find (or not find) the target.

Common Pitfalls to Avoid

Before we move on to actual C code, here are a few things that often trip up developers when working with binary search in C:

• Incorrect mid calculation: Instead of `(low + high)/2`, a safer version is `low + (high - low)/2` to avoid integer overflow.
• Missing condition to break the loop: Always ensure your loop terminates when `low > high`.
• Wrong update on pointers: Make sure you update `low = mid + 1` when the target is greater than `arr[mid]`, and `high = mid - 1` when it’s less.

Real-World Context

You’ll find binary search in C used in:

• Database index lookups
• Low-level memory scanning
• Compiler optimizations
• Searching logs, configs, or sorted files
• Libraries that implement functions like `bsearch()` in `<stdlib.h>`

The algorithm is more than just an interview question—it's a key tool in high-performance systems programming.

How To Implement Binary Search in C?

Now that we have a clear understanding of the theory behind binary search in C, let’s get into the actual implementation. In this section, we’ll implement binary search in C using both iterative and recursive methods. By the end, you will not only understand how to implement binary search but also why each step is essential.

1. Iterative Binary Search in C

The iterative approach to binary search is the more commonly used method because it’s generally more memory efficient. This is because it doesn’t require additional stack space as recursion does. Instead, it simply loops until the target element is found or the search space is exhausted.

Let’s dive deeper into the iterative binary search in C:

Code:

#include <stdio.h>

// Iterative Binary Search Function
int binarySearch(int arr[], int size, int target) {
    int low = 0;                // Start of the search range
    int high = size - 1;        // End of the search range

    // Loop until the search range is empty
    while (low <= high) {
        int mid = low + (high - low) / 2;  // Calculate the middle index

        // Check if the target is found
        if (arr[mid] == target) {
            return mid;  // Target found, return index
        }
        
        // If the target is greater than the middle element, discard the left half
        else if (arr[mid] < target) {
            low = mid + 1;  // Move the lower bound up
        }
        
        // If the target is less than the middle element, discard the right half
        else {
            high = mid - 1;  // Move the upper bound down
        }
    }

    return -1;  // Return -1 if target is not found
}

int main() {
    int arr[] = {2, 5, 9, 13, 18, 23, 37, 45};
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate size of the array
    int target = 23;  // Target to search for

    int result = binarySearch(arr, size, target);  // Call the binarySearch function

    // Print result
    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }

    return 0;
}

Output:

Element 23 found at index 5.

Detailed Explanation:

1. Initial Setup: 

We start by defining the `low` and `high` pointers, representing the search boundaries. Initially, `low` is set to 0 (the start of the array), and `high` is set to `size - 1` (the last index of the array).

2. Middle Element Calculation: 

In each iteration, we calculate the middle index `mid = low + (high - low) / 2`. This formula ensures that we don't encounter integer overflow (which could happen if we use `mid = (low + high) / 2` directly).

3. Comparison:

• We check if the element at `arr[mid]` matches the `target`. If it does, we return the index `mid`.
• If `arr[mid]` is less than `target`, we discard the left half of the search space by setting `low = mid + 1`.
• If `arr[mid]` is greater than `target`, we discard the right half of the search space by setting `high = mid - 1`.

4. Termination:

The loop continues until `low` exceeds `high`, meaning the search space is empty. If the target element is not found, we return `-1` to indicate failure. 

In addition, if you have any other operating system than Windows, you should explore our article on: 

• Compile C program on Linux 
• C Compiler for Mac

2. Recursive Binary Search in C

Now, let’s look at the recursive binary search in C. Recursion is often considered a more elegant approach because it simplifies the code. However, the recursive approach uses extra stack memory for each function call, which can be inefficient for large arrays. 

Code:

#include <stdio.h>

// Recursive Binary Search Function
int binarySearchRecursive(int arr[], int low, int high, int target) {
    // Base case: target not found
    if (low > high) {
        return -1;  // Return -1 if the search space is exhausted
    }

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

    // Check if the target is at the middle index
    if (arr[mid] == target) {
        return mid;  // Target found, return index
    }
    // If the target is greater than the middle element, search the right half
    else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, high, target);  // Recurse on the right half
    }
    // If the target is less than the middle element, search the left half
    else {
        return binarySearchRecursive(arr, low, mid - 1, target);  // Recurse on the left half
    }
}

int main() {
    int arr[] = {2, 5, 9, 13, 18, 23, 37, 45};
    int size = sizeof(arr) / sizeof(arr[0]);  // Calculate size of the array
    int target = 13;  // Target to search for

    int result = binarySearchRecursive(arr, 0, size - 1, target);  // Call the recursive function

    // Print result
    if (result != -1) {
        printf("Element %d found at index %d.\n", target, result);
    } else {
        printf("Element %d not found in the array.\n", target);
    }

    return 0;
}

Output:

Element 13 found at index 3.

Detailed Explanation:

1. Base Case: 

The base case checks if `low > high`, meaning the search space is empty. If so, the function returns `-1` to indicate that the target was not found.

2. Middle Element Calculation:

Like in the iterative version, we calculate `mid = low + (high - low) / 2`.

3. Recursive Calls:

• If `arr[mid]` matches the target, the function returns the index `mid`.
• If `arr[mid] < target`, the function recursively searches the right half by calling `binarySearchRecursive(arr, mid + 1, high, target)`.
• If `arr[mid] > target`, it searches the left half by calling `binarySearchRecursive(arr, low, mid - 1, target)`.

4. Termination:

The recursion continues until either the element is found or the search space becomes empty (i.e., `low > high`).

Iterative vs. Recursive: When to Use What?

Iterative Approach: This is typically more efficient when you’re working with large datasets, as it avoids the extra stack overhead from recursive calls.

Recursive Approach: Although it uses more memory, the recursive approach is often more elegant and easier to understand. It is perfect for smaller datasets or when you are focusing more on clarity and less on performance.

Space and Time Complexity of Binary Search in C

One of the biggest reasons why binary search in C is so popular is its efficiency. But how efficient is it, really? Let’s dive into the space and time complexity of the binary search algorithm and understand why it’s so powerful for large datasets.

Time Complexity of Binary Search

The time complexity of an algorithm tells you how the running time increases as the size of the input increases. In the case of binary search, the input is an array, and the size is the number of elements in that array.

How does binary search achieve this efficiency?

Binary search works by repeatedly halving the search space. Let’s say you start with an array of size `n`. Here’s what happens at each step:

1. First step: The array has `n` elements. You compare the middle element of the array (`arr[mid]`) with the target. If it’s not a match, you cut the search space in half (either the left half or the right half).

2. Second step: Now, you’re down to `n/2` elements. You repeat the process: compare the middle element of this smaller array with the target, and discard half of the array.

3. Third step: Now, you have `n/4` elements, and so on.

This halving process continues until the search space is reduced to a single element. Essentially, each comparison halves the search space, which is why binary search is so efficient.

The formula for time complexity:

• In the first step, we check 1 element.
• In the second step, we check 1 element out of `n/2`.
• In the third step, we check 1 element out of `n/4`.
• In general, after `k` steps, the size of the remaining array is `n / 2^k`.

The process stops when the search space is reduced to 1 element, which happens after approximately `log2(n)` steps. This is where the logarithmic time complexity comes in.

So, the time complexity of binary search is:

O(log n): In each step, we halve the search space, which leads to logarithmic time complexity.

What does this mean in practice?

• If you have an array of 1,000,000 elements, binary search will only require about 20 comparisons (since log2(1,000,000) ≈ 20).
• If you have 1 billion elements, binary search will still only require about 30 comparisons (log2(1,000,000,000) ≈ 30).

That’s the magic of binary search! Even for very large arrays, it remains fast and efficient.

Space Complexity of Binary Search

Now that we know the time complexity, let’s turn our attention to the space complexity. Space complexity refers to how much additional memory the algorithm requires, apart from the input data.

For binary search in C, there are two main implementations to consider:

1. Iterative binary search

2. Recursive binary search

Space Complexity of Iterative Binary Search

In the iterative version, we don’t need extra space for recursive function calls. All we do is manipulate indices (`low`, `high`, `mid`) and perform comparisons, which uses a constant amount of space.

Thus, the space complexity for iterative binary search is:

O(1): Constant space. We only need a few variables (`low`, `high`, `mid`) to store indices.

Space Complexity of Recursive Binary Search

In the recursive version, however, every recursive call adds a new frame to the call stack. The maximum depth of the recursion depends on how many times the search space can be halved, which is logarithmic in relation to the size of the array.

Therefore, the space complexity for recursive binary search is:

O(log n): Each recursive call takes up space on the stack, and there will be at most `log2(n)` recursive calls.

Pros and Cons of Binary Search in C

Binary search in C is a powerful and efficient algorithm that can significantly improve the performance of search operations in sorted datasets. However, like any algorithm, it comes with its advantages and disadvantages. Understanding both the pros and cons of binary search will help you determine when to use it effectively and when to consider alternative approaches. Below, we’ll explore the benefits and drawbacks of binary search in C.

Pros of Binary Search in C

Efficiency for Sorted Data  

One of the most significant benefits of binary search in C is its efficiency when dealing with sorted data. With a time complexity of O(log n), it dramatically reduces the search space by halving it with each comparison. This makes binary search much faster than linear search (O(n)), particularly for large datasets, and is highly effective when searching through large arrays or lists.

Low Space Complexity  

Another advantage is the low space complexity of binary search. When implemented iteratively, the space complexity is O(1), meaning it uses a minimal amount of extra memory. This makes binary search an excellent choice for systems with limited memory, as it does not require additional data structures or recursion stacks.

Predictable Performance  

The performance of binary search in C is predictable, as it consistently runs in O(log n) time, regardless of the dataset size. Whether you're searching in an array with hundreds or millions of elements, the time it takes to find the desired element remains relatively constant, making it a reliable choice for large datasets.

Versatility Across Data Structures  

While binary search is most commonly used on arrays, it can also be adapted for other sorted data structures, such as binary search trees (BSTs) or sorted linked lists. This versatility allows binary search to be applied in various scenarios where sorted data is present, making it a valuable tool in many algorithmic problems.

Cons of Binary Search in C

Requires Sorted Data  

The biggest limitation of binary search is that it requires the data to be sorted. If the dataset is unsorted, you must first sort it, which can add significant overhead. Sorting typically has a time complexity of O(n log n), which can negate the time advantages of binary search, especially when the dataset changes frequently.

Not Efficient for Small Datasets  

For small datasets, the overhead of binary search may not be worth the time saved. When dealing with a small number of elements (e.g., fewer than 10 or 20), the simplicity and low overhead of linear search may make it a better choice, as it can be more efficient for these scenarios.

Recursive Version Memory Overhead  

If you use the recursive version of binary search, there is a memory overhead due to the additional function calls. Each recursive call requires memory on the call stack, and for large datasets, this can lead to stack overflow or high memory usage. The iterative version avoids this issue and is often the preferred method for large arrays.

Limited to Random Access Data Structures  

Binary search requires random access to elements, meaning it only works with data structures like arrays where you can access any element directly by its index. It is unsuitable for linked lists, where elements must be accessed sequentially. In such cases, a linear search would be a more appropriate choice.

Inefficient for Dynamic Data  

When the data is dynamically changing—such as with frequent insertions, deletions, or updates—maintaining the sorted order required for binary search can become inefficient. Re-sorting the data or re-balancing the structure can be costly. In such cases, other data structures, such as hash tables or balanced trees, might offer better overall performance, as they support more efficient updates. 

Conclusion

In conclusion, binary search in C is a highly efficient algorithm for searching through sorted data, offering significant time and space advantages, especially for large datasets. Its O(log n) time complexity ensures that even with millions of elements, the algorithm performs quickly, making it an ideal choice for applications that require fast searching. The ability to implement it with low space complexity and predictable performance further adds to its appeal.

However, as with any algorithm, binary search has its limitations. It requires the data to be sorted, and for small datasets or dynamically changing data, its advantages may diminish. Additionally, its reliance on random access makes it unsuitable for certain data structures like linked lists. It’s important to carefully evaluate the specific requirements of your project before deciding whether binary search is the best solution.

Ultimately, when applied in the right context—on sorted datasets with large elements—binary search in C is a powerful tool that can optimize your program’s performance. Understanding both its pros and cons ensures that you can use it effectively, making it a valuable addition to your programming toolkit.

FAQs

1. What is the origin of binary search?  

Binary search has its roots in early computer science and was first used as a divide-and-conquer algorithm. It was introduced in the 1950s as a method to quickly search through sorted datasets. Over time, it became an essential technique for improving the efficiency of searching algorithms in computing, especially for large datasets.

2. Can binary search be used for searching in a string?  

Yes, binary search can be applied to search within a sorted string or an array of characters. The string must be sorted lexicographically before performing binary search. It is commonly used for tasks such as searching for words in a dictionary or finding a specific character in a sorted list of strings.

3. What are some common variations of binary search?  

There are several variations of binary search. Some of the common ones include searching for the first or last occurrence of an element in a sorted array, finding the correct insertion point for an element in a sorted array, and binary search on continuous values, where the search space is a range of numbers to find the optimal solution.

4. What is the best case time complexity of binary search?  

The best-case time complexity of binary search is O(1). This occurs when the middle element of the array is equal to the target value. In this case, binary search immediately finds the target in just one comparison, making it the most efficient scenario, with no further iterations required.

5. What happens if the target element is not in the array?  

If the target element is not present in the array, binary search will eventually reduce the search space to the point where the start index exceeds the end index. When this happens, the algorithm returns a “not found” result, typically -1 or some error code, indicating that the element doesn't exist in the array.

6. Can binary search be used on linked lists?  

Binary search is not suitable for linked lists because they do not allow random access to elements. Linked lists require sequential access, meaning you can't directly jump to the middle element as you can with arrays. This makes the use of binary search inefficient for linked lists, as it requires linear traversal instead.

7. Why is binary search faster than linear search?  

Binary search is faster than linear search because it reduces the search space by half with each iteration. With a time complexity of O(log n), it significantly improves search efficiency for large datasets. In contrast, linear search has a time complexity of O(n), meaning it checks each element one by one, making it slower for large datasets.

8. What is the maximum number of comparisons binary search makes?  

The maximum number of comparisons made by binary search occurs in the worst-case scenario when the target element is either not present or located at one of the extreme ends. For an array of size n, the maximum comparisons made are log2(n) + 1, which is significantly less than linear search’s n comparisons.

9. What is a binary search tree (BST), and how is it related to binary search?  

A binary search tree (BST) is a data structure where each node has two children: the left child has a smaller value, and the right child has a larger value. Binary search can be applied to efficiently search for values in a BST by traversing the tree, similar to how binary search works on sorted arrays.

10. Can binary search be adapted for searching in multidimensional data?  

Yes, binary search can be adapted to search in multidimensional data, such as in a 2D array or matrix. However, the process becomes more complex as it requires binary search to be performed on multiple dimensions. In such cases, the data structure must be sorted in a specific way to efficiently use binary search in multiple dimensions.

11. What are the limitations of binary search?  

While binary search is efficient, it has some limitations. It requires the data to be sorted, making it unsuitable for unsorted datasets unless they are first sorted. Additionally, binary search is not effective for small datasets, as its overhead can outweigh the benefits. It's also limited to data structures that allow random access to elements, like arrays. 

Take a Free C Programming Quiz

Answer quick questions and assess your C programming knowledge

Start Quiz