Binary Search Program in C (Algorithm & Code)

Instead of checking every single element one by one (like Linear Search), Binary Search repeatedly divides the search interval in half.

1. Find the middle element of the sorted array.
2. Compare the target value with the middle element.
3. If they match, the search is successful.
4. If the target is smaller than the middle element, it means the target must be in the left half. So, ignore the right half entirely.
5. If the target is larger, ignore the left half and search only in the right half.
6. Repeat the process until the target is found or the search space becomes zero.

#include <stdio.h>

// Binary search function
int binarySearch(int arr[], int left, int right, int target) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        // Check if target is present at mid
        if (arr[mid] == target)
            return mid;

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

        // If target is smaller, ignore right half
        else
            right = mid - 1;
    }
    // Target is not present in array
    return -1;
}

int main() {
    int arr[] = {2, 4, 8, 15, 23, 42, 55};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 23;
    
    int result = binarySearch(arr, 0, n - 1, target);
    
    if (result == -1)
        printf("Element is not present in array");
    else
        printf("Element is present at index %d", result);
        
    return 0;
}

Because it cuts the array size in half with every step, the time complexity is exceptionally fast.

• Best Case: O(1) (If the target happens to be the exact middle element on the first try).
• Worst Case & Average Case: O(log n)

(For example, if you have 1,000,000 sorted elements, a linear search might take 1,000,000 checks, but a binary search will find the target in a maximum of just 20 checks!)