#include <iostream>
using namespace std;
int binarySearchRecursive(int arr[], int left, int right, int key) {
if (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key) {
return mid; // Found at index mid
}
if (arr[mid] > key) {
return binarySearchRecursive(arr, left, mid - 1, key);
}
return binarySearchRecursive(arr, mid + 1, right, key);
}
return -1; // Not found
}
int main() {
int arr[] = {11, 12, 22, 25, 34, 64, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int key;
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
cout << "Enter element to search: ";
cin >> key;
int result = binarySearchRecursive(arr, 0, n - 1, key);
if (result != -1) {
cout << "Element found at index: " << result << endl;
} else {
cout << "Element not found in array" << endl;
}
return 0;
}Output
Sorted array: 11 12 22 25 34 64 90 Enter element to search: 25 Element found at index: 3
This program teaches you how to implement the Binary Search algorithm in C++ using a recursive approach. The recursive implementation uses function calls to divide the search space, making the code more elegant and easier to understand. While it has the same time complexity as the iterative version, it uses additional space for the recursion stack.
1. What This Program Does
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.
2. Header File Used
#include <iostream>
This header provides:
- cout for displaying output
- cin for taking input from the user
3. 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
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) {
return mid; // Found at index mid
}
if (arr[mid] > key) {
return binarySearchRecursive(arr, left, mid - 1, key);
}
return binarySearchRecursive(arr, mid + 1, right, key);
}
return -1; // Not found
}
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
5. 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
6. 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))
7. 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)
8. Recursive vs Iterative
Recursive Advantages:
- More elegant and readable code
- Closer to mathematical definition
- Easier to understand divide-and-conquer
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
9. 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)
10. return 0;
This ends the program successfully.
Summary
- Recursive Binary Search uses function calls to divide search space.
- Time complexity: O(log n) - same as iterative version.
- Space complexity: O(log n) - uses recursion stack.
- More elegant code but uses more memory than iterative version.
- Base case: left > right means key not found.
- Each recursive call handles smaller search interval.
- Understanding recursion is essential for advanced algorithms.
- Both recursive and iterative versions have same time complexity.
This program is fundamental for beginners learning recursion, understanding divide-and-conquer techniques, and preparing for advanced recursive algorithms in C++ programs.