Binary Search (Recursive)
Binary Search Algorithm in C++ (Recursive Implementation)
BeginnerTopic: Sorting & Searching Programs
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;
}Output
Sorted array: 11 12 22 25 34 64 90 Enter element to search: 25 Element found at index: 3
Understanding Binary Search (Recursive)
Binary Search recursive implementation uses function calls to divide the search space. Time Complexity: O(log n). Space Complexity: O(log n) due to recursion stack. It's more elegant but uses more memory than iterative version. Both implementations have the same time complexity.
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.