What Is Binary Search in Data Structure Using C?

In data structures, binary search is a widely used algorithm for searching an element in a sorted array or list. It follows the principle of divide and conquer to efficiently locate the Target element. Let’s dive deeper into understanding binary search and its implementation in C.

Working of Binary Search

Binary search works by repeatedly dividing the search space in half until the Target element is found or determined to be absent. Here are the steps involved:

1. Start with defining the lower and upper bounds of the search space. Initially, these bounds are set to the first and last elements of the array, respectively.
2. Calculate the middle index of the current search space using the formula: mid = (low + high) / 2.
3. If the middle element is equal to the Target element, return its index as the result.
4. If the middle element is greater than the Target element, update the upper bound as (mid – 1) and repeat from step 2.
5. If the middle element is less than the Target element, update the lower bound as (mid + 1) and repeat from step 2.

The process continues until either the Target element is found or it is determined that it does not exist in the array. Binary search halves its search space at every step, making it significantly faster than linear search for large datasets.

C Implementation

We can implement binary search in C using a function. Let’s take a look at an example:

#include <stdio.h>

int binarySearch(int arr[], int size, int Target) {
    int low = 0, high = size - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] == Target)
            return mid;
        
        if (arr[mid] < Target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    
    return -1; // Target element not found
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    int Target = 6;
    
    int result = binarySearch(arr, size, Target);
    
    if (result == -1)
        printf("Element not found\n");
    else
        printf("Element found at index %d\n", result);
    
    return 0;
}

In the above example, the binarySearch function takes an array arr, its size size, and the Target element target. It returns the index of the Target element if found, otherwise -1.

Conclusion

Binary search is a powerful searching algorithm that reduces the search space by half at each step. Its efficiency makes it suitable for searching large datasets. Understanding its working and implementing it in C can be beneficial for solving various programming problems.

I hope this article has provided you with a clear understanding of what binary search is and how it can be implemented in C. Happy coding!