Problem Statement

Write a program that implement binary search using recursion. The program should prompt the user to input a sorted array and a target element, and then determine whether the target element exists in the array or not.

Problem Understanding

Binary search is an efficient algorithm for finding a target element in a sorted array. It works by repeatedly dividing the search interval in half until the target element is found or the search interval is empty. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when the search interval is empty or when the target element is found.

Solution in C++

#include <iostream>
#include <vector>

// Recursive function to perform binary search
bool binarySearch(const std::vector<int>& arr, int target, int left, int right) {
    // Base case: If the search interval is empty
    if (left > right) {
        return false;
    }

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

    // If the target is found at the mid index
    if (arr[mid] == target) {
        return true;
    }
    // If the target is in the left half
    else if (target < arr[mid]) {
        return binarySearch(arr, target, left, mid - 1);
    }
    // If the target is in the right half
    else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

int main() {
    int n, target;

    // Prompt the user to enter the size of the array
    std::cout << "Enter the size of the sorted array: ";
    std::cin >> n;

    // Create a sorted array of size n
    std::vector<int> arr(n);

    // Prompt the user to enter the sorted elements of the array
    std::cout << "Enter the sorted elements of the array:\n";
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // Prompt the user to enter the target element
    std::cout << "Enter the target element to search: ";
    std::cin >> target;

    // Perform binary search
    bool found = binarySearch(arr, target, 0, n - 1);

    // Print the result
    if (found) {
        std::cout << "The target element is found in the array.\n";
    } else {
        std::cout << "The target element is not found in the array.\n";
    }

    return 0;
}

OR:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Recursive function for binary search
int binarySearch(vector<int>& arr, int left, int right, int target) {
    // Base case: If the search range is invalid
    if (left > right) {
        return -1; // Target not found
    }

    // Calculate the middle index
    int mid = left + (right - left) / 2;

    // Check if the target is at the middle index
    if (arr[mid] == target) {
        return mid; // Target found, return index
    } 
    // If the target is smaller, search in the left half
    else if (arr[mid] > target) {
        return binarySearch(arr, left, mid - 1, target);
    } 
    // If the target is larger, search in the right half
    else {
        return binarySearch(arr, mid + 1, right, target);
    }
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5, 6, 7}; // Input sorted array
    int target = 1; // Target value to find
    int result = binarySearch(arr, 0, arr.size() - 1, target); // Perform binary search
    if (result != -1) {
        cout << "Target found at index: " << result << endl;
    } else {
        cout << "Target not found in the array." << endl;
    }
    return 0;
}

Complexity Analysis

Time Complexity:

• At each level of recursion, the search interval is divided in half resulting in a time complexity of O(log n).
• At each level, we perform a constant amount of work (comparing each elements and updating search interval), which can be considered O(1).
• Therefore, the overall time complexity of the solution is O(log n), where n is the size of the array.

Space Complexity:

The space complexity of the solution is O(log n) as well, considering the recursive calls create a call stack with log(n) frames.