Binary Search (Recursive) in C++

Binary Search Algorithm in C++ (Recursive Implementation).

BeginnerSorting & Searching ProgramsExample 11 of 13

binary-search-recursive.cpp

1#include <iostream>
2using namespace std;
3
4int binarySearchRecursive(int arr[], int left, int right, int key) {
5    if (left <= right) {
6        int mid = left + (right - left) / 2;
7        
8        if (arr[mid] == key) {
9            return mid;  // Found at index mid
10        }
11        
12        if (arr[mid] > key) {
13            return binarySearchRecursive(arr, left, mid - 1, key);
14        }
15        
16        return binarySearchRecursive(arr, mid + 1, right, key);
17    }
18    
19    return -1;  // Not found
20}
21
22int main() {
23    int arr[] = {11, 12, 22, 25, 34, 64, 90};
24    int n = sizeof(arr) / sizeof(arr[0]);
25    int key;
26    
27    cout << "Sorted array: ";
28    for (int i = 0; i < n; i++) {
29        cout << arr[i] << " ";
30    }
31    cout << endl;
32    
33    cout << "Enter element to search: ";
34    cin >> key;
35    
36    int result = binarySearchRecursive(arr, 0, n - 1, key);
37    
38    if (result != -1) {
39        cout << "Element found at index: " << result << endl;
40    } else {
41        cout << "Element not found in array" << endl;
42    }
43    
44    return 0;
45}

Output

Sorted array: 11 12 22 25 34 64 90
Enter element to search: 25
Element found at index: 3

What's going on

The program searches for an element in a sorted array using Binary Search (recursive version). For example:

Sorted array: [11, 12, 22, 25, 34, 64, 90]

Search for: 25

Result: Element found at index 3

The recursive version divides the problem into smaller subproblems by calling itself with a smaller search interval.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

Understanding Recursive Binary Search

Algorithm Concept

Base case: if left > right, key not found

Recursive case: divide interval and search appropriate half

Each recursive call handles smaller subproblem

More elegant but uses recursion stack

Visual Example

Array: [11, 12, 22, 25, 34, 64, 90]

Search for: 25

Call 1: binarySearch(arr, 0, 6, 25)

mid = 3, arr[3] = 25 → match! Return 3

Example (searching for 34):

Call 1: binarySearch(arr, 0, 6, 34)

mid = 3, arr[3] = 25 < 34 → Call 2: binarySearch(arr, 4, 6, 34)

Call 2: binarySearch(arr, 4, 6, 34)

mid = 5, arr[5] = 64 > 34 → Call 3: binarySearch(arr, 4, 4, 34)

Call 3: binarySearch(arr, 4, 4, 34)

mid = 4, arr[4] = 34 → match! Return 4

Function: binarySearchRecursive()

int binarySearchRecursive(int arr[], int left, int right, int key) {

if (left <= right) {

int mid = left + (right - left) / 2;

if (arr[mid] == key) {

}

if (arr[mid] > key) {

return binarySearchRecursive(arr, left, mid - 1, key);

}

return binarySearchRecursive(arr, mid + 1, right, key);

}

return -1; // Not found

}

1return mid;  // Found at index mid

How it works

Base case: if left > right, return -1 (not found)

Calculate mid index

If match: return mid

If key < arr[mid]: recursively search left half

If key > arr[mid]: recursively search right half

Step-by-Step Recursion

Base Case

if (left > right): search interval is empty

Key not found, return -1

Recursive Cases

if (arr[mid] == key): found, return mid

if (arr[mid] > key): search left half [left, mid-1]

if (arr[mid] < key): search right half [mid+1, right]

Recursion Tree

(searching for 34):

binarySearch(arr, 0, 6, 34)

mid=3, arr[3]=25 < 34

→ binarySearch(arr, 4, 6, 34)

mid=5, arr[5]=64 > 34

→ binarySearch(arr, 4, 4, 34)

mid=4, arr[4]=34 == 34

→ return 4

Time and Space Complexity

Time Complexity

: O(log n)

Same as iterative version

Each recursive call eliminates half the elements

Maximum depth: log₂(n) recursive calls

Space Complexity

: O(log n)

Recursion stack depth: log₂(n)

Each recursive call uses stack space

More memory than iterative version (O(1))

When to Use Recursive Binary Search

Best For

When code elegance is preferred

Teaching recursion concepts

When stack space is not a concern

Smaller arrays (stack depth is manageable)

Not Recommended For

Very large arrays (deep recursion stack)

Memory-constrained environments

When O(1) space is required

Performance-critical applications (slight overhead)

Recursive vs Iterative

Recursive Advantages

Recursive Disadvantages

Uses O(log n) stack space

Function call overhead

Risk of stack overflow for very deep recursion

Iterative Advantages

O(1) space complexity

No function call overhead

No stack overflow risk

Iterative Disadvantages

Slightly more complex loop logic

Less elegant code

Important Considerations

Base Case

if (left <= right): valid interval, continue search

if (left > right): empty interval, return -1

Critical for correct termination

Recursive Calls

left = mid - 1: exclude mid (already checked)

right = mid + 1: exclude mid (already checked)

Prevents infinite recursion

Stack Depth

Maximum depth: log₂(n)

For n=1000000: ~20 levels (manageable)

For n=10⁹: ~30 levels (still manageable)

return 0;

This ends the program successfully.

PreviousBinary Search (Iterative)NextJump Search