Binary Search in C

Binary search is a widely used searching algorithm that requires the array to be sorted before search is applied. It is a divide and conquer algorithm which compares the middle element of the array with the target value, and if they are unequal, the half in which the target cannot lie is eliminated.

Key Characteristics of Binary Search

• Sorted Data: The array must be sorted in ascending or descending order.
• Efficient: Binary search has a time complexity of O(log n), making it significantly faster than linear search algorithms.

How Binary Search Works

The binary search algorithm can be divided into the following steps:

1. Step 1: Find the middle element of the array.
2. Step 2: If the target value is equal to the middle element of the array, return the middle element's index.
3. Step 3: If the target value is less than the middle element, repeat the process with the left half of the array.
4. Step 4: If the target value is greater than the middle element, repeat the process with the right half of the array.
5. Step 5: Repeat steps 1-4 until the target value is found or the subarray reduces to zero.

Here is a simple implementation of binary search in C:

#include <stdio.h>

int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // If the element is present at the middle
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        // Else the element can only be present in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }

    // We reach here when element is not present in array
    return -1;
}

int main(void)
{
    int arr[] = {2, 3, 4, 10, 40};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 10;
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? printf("Element is not present in array")
                   : printf("Element is present at index %d", result);
    return 0;
}

This code will search for the number 10 in the array and output its index.

Time Complexity

The time complexity of Binary Search can be written as T(n) = T(n/2) + c. The time complexity of this algorithm is O(log n).

Conclusion

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.