C Program for Binary Search Using Recursion

A C program for binary search using recursion defines a function like int binarySearch(int arr[], int low, int high, int x) that calls itself to divide the search range until the element is found or the range is empty.

Examples

Inputarr = {2, 4, 6, 8, 10}, x = 6

OutputElement found at index 2

Inputarr = {1, 3, 5, 7, 9}, x = 4

OutputElement not found

Inputarr = {10}, x = 10

OutputElement found at index 0

How to Think About It

To perform binary search recursively, start by checking the middle element of the array. If it matches the target, return its index. If the target is smaller, repeat the search on the left half; if larger, on the right half. Keep dividing the array until the element is found or the search range is empty.

Algorithm

1

Start with the full array range from low to high indices.

2

Find the middle index of the current range.

3

Compare the middle element with the target value.

4

If equal, return the middle index.

5

If target is smaller, recursively search the left half.

6

If target is larger, recursively search the right half.

7

If low exceeds high, return -1 indicating not found.

Code

c

#include <stdio.h>

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

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int result = binarySearch(arr, 0, n - 1, x);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

Output

Element found at index 2

Dry Run

Let's trace searching for 6 in the array {2, 4, 6, 8, 10} using recursion.

1

Initial call

low=0, high=4, mid=2, arr[mid]=6, target=6

2

Check middle element

arr[mid] == target, return index 2

Call	low	high	mid	arr[mid]	Action
1	0	4	2	6	Found element, return 2

Why This Works

Step 1: Divide the array

The function calculates the middle index to split the array into two halves using mid = low + (high - low) / 2.

Step 2: Compare middle element

It compares the middle element with the target value to decide which half to search next.

Step 3: Recursive search

The function calls itself recursively on the left or right half until the element is found or the search range is empty.

Alternative Approaches

Iterative binary search

c

#include <stdio.h>

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

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int result = binarySearchIter(arr, n, x);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

This uses a loop instead of recursion, which can be more memory efficient by avoiding function call overhead.

Recursive binary search with helper function

c

#include <stdio.h>

int binarySearchHelper(int arr[], int low, int high, int x) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (arr[mid] == x) return mid;
    else if (arr[mid] > x) return binarySearchHelper(arr, low, mid - 1, x);
    else return binarySearchHelper(arr, mid + 1, high, x);
}

int binarySearch(int arr[], int n, int x) {
    return binarySearchHelper(arr, 0, n - 1, x);
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int result = binarySearch(arr, n, x);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

This separates the recursive logic into a helper function for cleaner main function interface.

Complexity: O(log n) time, O(log n) space

Time Complexity

Binary search divides the search space in half each time, so it runs in logarithmic time, O(log n).

Space Complexity

Recursive calls add to the call stack, so space complexity is O(log n) due to recursion depth.

Which Approach is Fastest?

Iterative binary search uses O(1) space and is generally faster due to no recursion overhead, but recursive is easier to understand.

Approach	Time	Space	Best For
Recursive binary search	O(log n)	O(log n)	Clear recursive logic, teaching
Iterative binary search	O(log n)	O(1)	Memory efficiency, performance
Recursive with helper	O(log n)	O(log n)	Cleaner code interface