C++ Program for Binary Search Using Recursion

A C++ program for binary search using recursion calls a function that checks the middle element and recursively searches the left or right half using int binarySearch(int arr[], int left, int right, int target).

Examples

Inputarr = {1, 3, 5, 7, 9}, target = 7

OutputElement found at index 3

Inputarr = {2, 4, 6, 8, 10}, target = 5

OutputElement not found

Inputarr = {10}, target = 10

OutputElement found at index 0

How to Think About It

To do a binary search with recursion, first find the middle of the current array segment. If the middle element is the target, return its position. If the target is smaller, search the left half by calling the function again with updated boundaries. If larger, search the right half similarly. Stop when the segment is empty.

Algorithm

1

Start with the full array and target value.

2

Find the middle index between left and right boundaries.

3

If middle element equals target, return middle index.

4

If target is less than middle element, recursively search left half.

5

If target is greater than middle element, recursively search right half.

6

If left boundary exceeds right, return -1 to indicate not found.

Code

cpp

#include <iostream>
using namespace std;

int binarySearch(int arr[], int left, int right, int target) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
    else return binarySearch(arr, mid + 1, right, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int result = binarySearch(arr, 0, n - 1, target);
    if (result != -1) cout << "Element found at index " << result << endl;
    else cout << "Element not found" << endl;
    return 0;
}

Output

Element found at index 3

Dry Run

Let's trace searching for 7 in the array {1, 3, 5, 7, 9} using recursion.

1

Initial call

left=0, right=4, mid=2, arr[mid]=5, target=7

2

Target greater than mid element

Search right half: left=3, right=4

3

Second call

left=3, right=4, mid=3, arr[mid]=7, target=7

4

Element found

Return index 3

Call	Left	Right	Mid	arr[Mid]	Target	Action
1	0	4	2	5	7	Search right half
2	3	4	3	7	7	Found element

Why This Works

Step 1: Divide the array

The code finds the middle index using mid = left + (right - left) / 2 to avoid overflow and splits the array into halves.

Step 2: Compare middle element

It compares the middle element with the target using if (arr[mid] == target) to check if the search is done.

Step 3: Recursive search

If not found, it calls itself recursively on the left or right half depending on whether the target is smaller or larger than the middle element.

Alternative Approaches

Iterative binary search

cpp

#include <iostream>
using namespace std;

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

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    int result = binarySearchIter(arr, n, target);
    if (result != -1) cout << "Element found at index " << result << endl;
    else cout << "Element not found" << endl;
    return 0;
}

Uses a loop instead of recursion, saving stack space and often faster for large arrays.

Using std::binary_search from <algorithm>

cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 7;
    bool found = binary_search(arr, arr + n, target);
    if (found) cout << "Element found" << endl;
    else cout << "Element not found" << endl;
    return 0;
}

Standard library function that performs binary search efficiently but does not return index.

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

Time Complexity

Each recursive call halves the search space, so the number of calls is proportional to log base 2 of the array size.

Space Complexity

Recursion uses stack space proportional to the depth of calls, which is O(log n). Iterative approach uses O(1) space.

Which Approach is Fastest?

Iterative binary search is generally faster and uses less memory than recursion, but recursion is easier to understand and implement.

Approach	Time	Space	Best For
Recursive binary search	O(log n)	O(log n)	Simple code, teaching recursion
Iterative binary search	O(log n)	O(1)	Performance and memory efficiency
std::binary_search	O(log n)	O(1)	Quick use with standard library