Binary Search in C – Iterative and Recursive with Example

Binary search in C finds a target value in a sorted array by repeatedly halving the search space. At each step it compares the target against the middle element: if they match, the search is done; if the target is smaller, discard the right half; if larger, discard the left half. This gives O(log n) time — for one million elements, at most 20 comparisons.

This page covers the iterative version, the recursive version, and why the array must be sorted before calling binary search.

How Binary Search Works — Step by Step

Example: Find 27 in [3, 9, 10, 27, 38, 43, 82]

Array:  [ 3,  9, 10, 27, 38, 43, 82 ]
Index:    0   1   2   3   4   5   6

Step 1: low=0, high=6, mid=3  → arr[3]=27 == target → FOUND at index 3

--- another example: find 10 ---
Step 1: low=0, high=6, mid=3  → arr[3]=27 > 10 → search left: high=2
Step 2: low=0, high=2, mid=1  → arr[1]=9  < 10 → search right: low=2
Step 3: low=2, high=2, mid=2  → arr[2]=10 == 10 → FOUND at index 2

--- find 50 (not present) ---
Step 1: low=0, high=6, mid=3  → arr[3]=27 < 50 → low=4
Step 2: low=4, high=6, mid=5  → arr[5]=43 < 50 → low=6
Step 3: low=6, high=6, mid=6  → arr[6]=82 > 50 → high=5
Now low > high → NOT FOUND

Binary Search in C — Iterative Version

#include <stdio.h>

int binarySearch(int arr[], int n, int target)
{
    int low = 0, high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  /* avoids overflow vs (low+high)/2 */

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;  /* not found */
}

int main(void)
{
    int arr[] = {3, 9, 10, 27, 38, 43, 82};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target, result;

    printf("Enter target value: ");
    scanf("%d", &target);

    result = binarySearch(arr, n, target);

    if (result != -1)
        printf("Found at index %d.\n", result);
    else
        printf("%d not found in the array.\n", target);

    return 0;
}

How to Compile and Run

gcc -Wall -o bsearch bsearch.c
./bsearch

Sample Output

Enter target value: 27
Found at index 3.

Enter target value: 50
50 not found in the array.

Recursive Binary Search

#include <stdio.h>

int binarySearchRecursive(int arr[], int low, int high, int target)
{
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;

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

int main(void)
{
    int arr[] = {3, 9, 10, 27, 38, 43, 82};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target, result;

    printf("Enter target value: ");
    scanf("%d", &target);

    result = binarySearchRecursive(arr, 0, n - 1, target);

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

    return 0;
}

Time and Space Complexity

Each iteration halves the search space. Starting with n elements: after 1 step → n/2, after 2 → n/4, … after k steps → n/2ᵏ. The search ends when n/2ᵏ < 1, so k = log₂(n). For n = 1,000,000 that is ≤ 20 steps.

Binary Search vs Linear Search

What This Program Teaches

• Why mid = low + (high - low) / 2 instead of (low + high) / 2 — the latter overflows when both indices exceed INT_MAX / 2
• The loop invariant: if the target exists, it is always within [low, high] — once low > high, the target is absent
• Binary search only works on sorted data — applying it to an unsorted array gives wrong answers with no error
• The recursive version is elegant but adds O(log n) stack frames — prefer iterative for large n

Related Programs

• Merge Sort in C — Produces a Sorted Array
• Quick Sort in C
• Insertion Sort in C
• C Aptitude Questions and Answers

As an Amazon Associate we earn from qualifying purchases.

Recommended Book

Arrays, pointers, and search algorithms are all covered in The C Programming Language by Kernighan & Ritchie — includes the classic binary search example in chapter 3. Also on Amazon.com.