How to Perform Binary Search on a Sorted Array in C

Binary Search on a Sorted Array in C

Binary search is an efficient algorithm to find an element in a sorted array. It works by repeatedly dividing the array into two halves and checking whether the middle element is the target value. If the middle element is greater, the search continues in the left half; otherwise, it moves to the right half. This method significantly reduces the number of comparisons compared to linear search.

---

Binary Search Algorithm

The binary search algorithm follows these steps:

1. Find the middle element of the array.
2. If the middle element matches the target value, return the index.
3. If the middle element is greater than the target, search in the left half.
4. If the middle element is smaller than the target, search in the right half.
5. Repeat the process until the element is found or the search space is exhausted.

Examples of Binary Search in C

1. Binary Search Using Iteration

In this example, we will implement binary search using an iterative approach. The function will take a sorted array and a target value as inputs and return the index of the target if found, otherwise -1.

main.c

#include <stdio.h>

// Function to perform binary search iteratively
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return -1; // Element not found
}

int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 30;
    
    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;
}

Explanation:

1. We define the function binarySearch() which takes an array, its size, and the target value as arguments.
2. We initialize two pointers, left and right, to mark the search boundaries.
3. We calculate the middle index mid using mid = left + (right - left) / 2.
4. If arr[mid] matches the target, we return mid.
5. If the target is greater than arr[mid], we update left to search in the right half.
6. If the target is smaller, we update right to search in the left half.
7. If the element is not found, we return -1.

Output:

Element found at index 2

2. Binary Search Using Recursion

In this example, we implement binary search using recursion. The function repeatedly calls itself with updated search boundaries.

main.c

#include <stdio.h>

// Recursive function to perform binary search
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right)
        return -1;

    int mid = left + (right - left) / 2;

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        return binarySearchRecursive(arr, mid + 1, right, target);
    else
        return binarySearchRecursive(arr, left, mid - 1, target);
}

int main() {
    int arr[] = {5, 15, 25, 35, 45, 55, 65};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 45;
    
    int result = binarySearchRecursive(arr, 0, size - 1, target);

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

    return 0;
}

Explanation:

1. We define the function binarySearchRecursive() that takes the array, left index, right index, and target value.
2. If left > right, it returns -1, indicating that the element is not present.
3. We calculate the middle index mid using mid = left + (right - left) / 2.
4. If arr[mid] matches the target, we return mid.
5. If the target is greater, we recursively call the function for the right half.
6. If the target is smaller, we recursively call the function for the left half.

Output:

Element found at index 4

Conclusion

In this tutorial, we explored binary search in C:

1. Iterative Binary Search: Uses a loop to divide and search.
2. Recursive Binary Search: Uses function calls to divide and search.

Binary search is an optimal way to search in sorted arrays with a time complexity of O(log n), making it significantly faster than linear search.