2- Binary Search

#include <iostream>
#include <vector>
using namespace std;

// Recursive Binary Search function
// Parameters:
// - arr: the sorted array we’re searching
// - left: the starting index of the current search range
// - right: the ending index of the current search range
// - target: the number we’re looking for
int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) 
{
    // Base case: if the search range is invalid (left > right), target is not found
    if (left > right)
        return -1; // return -1 to signal "not found"

    // Find the middle index of the current range
    int mid = left + (right - left) / 2;

    // Case 1: If the middle element matches the target, we found it
    if (arr[mid] == target)
        return mid;

    // Case 2: If the target is larger than the middle element, it must be in the right half of the array
    else if (arr[mid] < target)
        return binarySearchRecursive(arr, mid + 1, right, target);

    // Case 3: If the target is smaller than the middle element, it must be in the left half of the array
    else
        return binarySearchRecursive(arr, left, mid - 1, target);
}

int main() 
{
    // Define a sorted array (binary search only works on sorted data)
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};

    // Target value to search for
    int target = 7;

    // Call recursive binary search on the full array (indexes 0 → size-1)
    int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);

    // Check result: if -1, not found; otherwise print index
    if (result != -1)
        cout << "Found " << target << " at index " << result << endl;
    else
        cout << target << " not found" << endl;

    return 0;
}