Binary Search (Recursive)
Binary Search Algorithm in C++ (Recursive Implementation)
C++ Binary Search (Recursive) Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#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;
}Sorted array: 11 12 22 25 34 64 90 Enter element to search: 25 Element found at index: 3
Understanding Binary Search (Recursive)
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:
The recursive version divides the problem into smaller subproblems by calling itself with a smaller search interval.
---
2. Header File Used
This header provides:
---
#include <iostream>3. Understanding Recursive Binary Search
Algorithm Concept
:
Visual Example
:
Example (searching for 34):
---
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
}
return mid; // Found at index midHow it works
:
---
5. Step-by-Step Recursion
Base Case
:
Recursive Cases
:
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)
Space Complexity
: O(log n)
---
7. When to Use Recursive Binary Search
Best For
:
Not Recommended For
:
---
8. Recursive vs Iterative
Recursive Advantages
:
Recursive Disadvantages
:
Iterative Advantages
:
Iterative Disadvantages
:
---
9. Important Considerations
Base Case
:
Recursive Calls
:
Stack Depth
:
---
10. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for beginners learning recursion, understanding divide-and-conquer techniques, and preparing for advanced recursive algorithms in C++ programs.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Binary Search (Recursive)
This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.