Binary Search Algorithm in C Programming

Binary search uses a 'divide and conquer' strategy. Instead of checking every single element one by one (Linear Search), it repeatedly divides the array in half.

Imagine searching for the word 'Mango' in a dictionary. You don't read from page 1. You open the book to the middle. If you land on 'Orange', you know 'Mango' must be in the left half, so you completely ignore the right half. You open the left half to the middle, and repeat until you find it.

1. Find the middle element of the sorted array.
2. Compare the search key with the middle element.
3. If it matches, return the index.
4. If the search key is smaller than the middle element, it must lie in the left half. Update the 'high' pointer to mid - 1.
5. If the search key is larger, it must lie in the right half. Update the 'low' pointer to mid + 1.
6. Repeat until the item is found or the low pointer exceeds the high pointer (item not found).

#include <stdio.h>

int binarySearch(int arr[], int size, int key) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        
        if (arr[mid] == key)
            return mid; // Found the key
            
        if (arr[mid] < key)
            low = mid + 1; // Ignore left half
        else
            high = mid - 1; // Ignore right half
    }
    return -1; // Key not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 23;
    int result = binarySearch(arr, size, key);
    if(result == -1)
        printf("Element not found");
    else
        printf("Element found at index %d", result);
    return 0;
}

Because the search space is cut in half at every step, the time complexity of Binary Search is extremely fast: O(log n). To put this in perspective, if you search an array of 1 million elements, a Linear Search could take 1 million steps, but a Binary Search will find the answer in a maximum of just 20 steps!