Binary Search in C

Binary search is an efficient search algorithm that works only on sorted data. It is based on the principle of dividing the search space in half until the target value is found. This algorithm is much faster than linear search, especially when dealing with large datasets. In this article we are going to implement Binary Search in C language.

How Binary Search Works

Binary search works on the principle of divide and conquer. It repeatedly divides the sorted array in half and checks whether the desired element lies in the left or right half. Here are the steps of Binary Search –

1. Sorting: Binary search requires the array to be sorted in ascending or descending order for accurate results.
2. Initialization: Set the low and high indices to the start and end of the array, respectively.
3. Finding the Midpoint: Calculate the midpoint index by low + (high – low) / 2.
4. Comparison: Compare the midpoint element with the target value.
5. Adjusting Indices: Update the low and high indices based on the comparison result, narrowing down the search range.
6. Repeat: Continue the process until the element is found or the search range becomes empty.

Implementation of Binary Search in C

Here’s a simple implementation of the binary search algorithm in C for searching an element in a sorted array –

#include <stdio.h>

int binarySearch(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // If the target is found at the midpoint
        if (arr[mid] == target)
            return mid;

        // If the target is greater, ignore left half
        if (arr[mid] < target)
            low = mid + 1;

        // If the target is smaller, ignore right half
        else
            high = mid - 1;
    }

    // Target not found in the array
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 23;

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

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

    return 0;
}

Output

Time Complexity of Binary Search

Binary search is a very efficient search algorithm, with a time complexity of O(log n), where n is the size of the input data. This means that the time it takes to search for a value using binary search grows logarithmically with the size of the input data. This is much faster than linear search, which has a time complexity of O(n).

See Also

• C Code for Factorial
• Factorial in C++
• C Code for Prime Number
• C Program to Print Sum of Even and Odd Numbers
• C Code for Addition of Two Numbers