How does binary search work in C++ using recursion?

Can you explain how binary search works in C++ using recursion?

Sure! Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half.

How do I implement it in C++?

Here's a simple implementation:

int binarySearch(int arr[], int left, int right, int x) {
    if (right >= left) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == x) return mid;

        if (arr[mid] > x) return binarySearch(arr, left, mid - 1, x);

        return binarySearch(arr, mid + 1, right, x);
    }
    return -1; // Element not found
}

What are the advantages of using recursion for binary search?

Recursion simplifies the code and makes it easier to read. However, it can use more memory due to function call overhead.

Are there any downsides to using recursion?

Yes, recursion can lead to stack overflow if the recursion depth is too high, and it may be less efficient than iterative solutions in some cases.