Binary Search in C

Analogy categoryAnalogies

1. Introduction

Binary search is a fast searching algorithm used to find the position of a target value within a sorted array. Instead of checking every element one by one like linear search, binary search repeatedly divides the search range in half, eliminating half of the remaining elements at each step. Because of this halving strategy, binary search runs in O(log n) time, making it dramatically faster than linear search for large datasets. The only requirement is that the input array must already be sorted, since the algorithm relies on comparing the target with the middle element to decide which half to search next.

🏏

Cricket analogy: A scorer hunting for the over in which Virat Kohli reached his century doesn't read the scorecard ball by ball; he flips to the middle over, checks if the total is higher or lower, and repeats, cutting the search in half like binary search on a sorted innings log.

Binary search only works correctly on a sorted array. If the array is unsorted, you must sort it first (for example with quick sort or merge sort) before applying binary search.

2. Syntax

int binarySearch(int arr[], int low, int high, int key);

/* Parameters:
   arr  - sorted array of integers
   low  - starting index of the search range (initially 0)
   high - ending index of the search range (initially n - 1)
   key  - value to search for

   Returns the index of key if found, otherwise -1 */

3. Explanation

The algorithm maintains two pointers, low and high, that mark the current search range. At each step it computes mid = low + (high - low) / 2 to avoid integer overflow, then compares arr[mid] with the key. If they are equal, the search is done. If key is smaller than arr[mid], the target must lie in the left half, so high is updated to mid - 1. If key is larger, the target must lie in the right half, so low is updated to mid + 1. This process repeats until low exceeds high, at which point the key is not present in the array.

🏏

Cricket analogy: Setting low to the first over and high to the last over of an innings, a scorer computes mid to avoid overflow, checks that over's total against the target score, and moves low or high inward until the exact over is pinned down.

Worked trace: search for key = 23 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0-9). Initially low = 0, high = 9, mid = 4, arr[4] = 16. Since 23 > 16, set low = 5. Now low = 5, high = 9, mid = 7, arr[7] = 56. Since 23 < 56, set high = 6. Now low = 5, high = 6, mid = 5, arr[5] = 23. Match found at index 5, so the search terminates after just three comparisons instead of checking all ten elements.

🏏

Cricket analogy: Searching a sorted list of ten historic totals [2,5,8,12,16,23,38,56,72,91] for 23, a statistician checks index 4 (16), moves right past it, checks index 7 (56), moves left, then lands on index 5 (23) in just three lookups instead of ten.

4. Example

#include <stdio.h>

int binarySearch(int arr[], int low, int high, int key) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

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

    int result = binarySearch(arr, 0, n - 1, key);

    if (result != -1) {
        printf("Element %d found at index %d\n", key, result);
    } else {
        printf("Element %d not found in array\n", key);
    }
    return 0;
}

5. Output

text

Element 23 found at index 5

6. Key Takeaways

Binary search requires the array to be sorted beforehand; it does not work on unsorted data.
Time complexity is O(log n) for best, average, and worst case searches.
Space complexity is O(1) for the iterative version and O(log n) for the recursive version due to call stack usage.
Use mid = low + (high - low) / 2 instead of (low + high) / 2 to prevent integer overflow on large arrays.
Binary search is far more efficient than linear search, which is O(n), especially as the dataset grows large.