Searching is a fundamental operation in computer science and is used extensively in various applications. Binary search is a widely used algorithm for searching in sorted arrays or lists. It follows a divide-and-conquer strategy, making it highly efficient for large datasets. In this article, we will explore the recursive implementation of the binary search algorithm and understand how it works.

Recursive Binary Search Algorithm: The recursive binary search algorithm divides the search space in half by comparing the target element with the middle element of the array or list. Based on the comparison, it recursively continues the search on either the left or right half until the target element is found or the search space is empty.

Explore Free Engineering Handwritten Notes!

Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?

Download Now

We earn a commission if you make a purchase, at no additional cost to you.

Recursive Binary Search Code

Code in Python

def recursive_binary_search(arr, target, low, high):
    if low > high:
        return -1  # Base case: element not found

    mid = (low + high) // 2  # Calculate the middle index

    if arr[mid] == target:
        return mid  # Base case: element found

    elif arr[mid] > target:
        return recursive_binary_search(arr, target, low, mid - 1)  # Search in the left half

    else:
        return recursive_binary_search(arr, target, mid + 1, high)  # Search in the right half

Explanation of the Code: The recursive_binary_search function takes four parameters: the array or list (arr), the target element to search for, the lower index (low), and the higher index (high) of the search space.

The base case of the recursion is when the lower index (low) becomes greater than the higher index (high), indicating that the target element is not present in the search space. In such cases, the function returns -1 to signify the absence of the element.

The function calculates the middle index (mid) as the average of the lower and higher indices. It then compares the element at the middle index (arr[mid]) with the target element. If they are equal, the function returns the middle index, indicating that the target element has been found.

If the middle element is greater than the target, the search continues in the left half of the search space. The recursive_binary_search function is called again with the updated lower index (low) and the middle index minus one (mid – 1).

If the middle element is less than the target, the search continues in the right half of the search space. The recursive_binary_search function is called again with the updated middle index plus one (mid + 1) and the higher index (high).

The recursion continues until the base case is reached, and the final result is returned.

Code in C++

// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;

// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
	if (r >= l) {
		int mid = l + (r - l) / 2;

		// If the element is present at the middle
		// itself
		if (arr[mid] == x)
			return mid;

		// If element is smaller than mid, then
		// it can only be present in left subarray
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		// Else the element can only be present
		// in right subarray
		return binarySearch(arr, mid + 1, r, x);
	}

	// We reach here when element is not
	// present in array
	return -1;
}

// Driver code
int main()
{
	int arr[] = { 2, 3, 4, 10, 40 };
	int x = 10;
	int n = sizeof(arr) / sizeof(arr[0]);
	int result = binarySearch(arr, 0, n - 1, x);
	(result == -1)
		? cout << "Element is not present in array"
		: cout << "Element is present at index " << result;
	return 0;
}

Code in Java

// Java implementation of recursive Binary Search
class BinarySearch {

	// Returns index of x if it is present in arr[l..
	// r], else return -1
	int binarySearch(int arr[], int l, int r, int x)
	{
		if (r >= l) {
			int mid = l + (r - l) / 2;

			// If the element is present at the
			// middle itself
			if (arr[mid] == x)
				return mid;

			// If element is smaller than mid, then
			// it can only be present in left subarray
			if (arr[mid] > x)
				return binarySearch(arr, l, mid - 1, x);

			// Else the element can only be present
			// in right subarray
			return binarySearch(arr, mid + 1, r, x);
		}

		// We reach here when element is not present
		// in array
		return -1;
	}

	// Driver code
	public static void main(String args[])
	{
		BinarySearch ob = new BinarySearch();
		int arr[] = { 2, 3, 4, 10, 40 };
		int n = arr.length;
		int x = 10;
		int result = ob.binarySearch(arr, 0, n - 1, x);
		if (result == -1)
			System.out.println(
				"Element is not present in array");
		else
			System.out.println(
				"Element is present at index " + result);
	}
}

Time and Space Complexity of Recursive Binary Search

Recursive binary search has a time complexity of O(log n), where n is the size of the array or list. This is because the search space is halved with each recursive call. The space complexity is O(log n) as well, due to the recursive function calls and the call stack.

Advantages of Recursive Binary Search

Recursive binary search offers several advantages:

1. Simplicity: The recursive implementation is often more concise and easier to understand compared to its iterative counterpart.
2. Elegance: The divide and conquer approach of recursive binary search provides an elegant solution for searching in sorted arrays.
3. Code Reusability: Recursive binary search can be implemented as a separate function and reused in different parts of a program.
4. Readability: Recursive algorithms can closely resemble the mathematical or conceptual description of a problem, making the code more readable and maintainable.

Disadvantages of Recursive Binary Search

While recursive binary search has its advantages, it also has some drawbacks:

1. Space Complexity: Recursive calls consume additional memory on the call stack, which can be a concern for large arrays or deep recursion.
2. Stack Overflow: If the recursion depth becomes too large, it can result in a stack overflow error, terminating the program.
3. Iterative Conversion Difficulty: Converting a recursive binary search to an iterative implementation can be challenging for some programmers.

Conclusion

Recursive binary search is a powerful and efficient algorithm for searching in sorted arrays or lists. By dividing the search space in half at each step, it significantly reduces the number of comparisons required to find the target element. The recursive implementation allows for a concise and elegant code structure, making it easy to understand and implement.

Remember to ensure that the input array or list is sorted before using binary search, as the algorithm relies on this assumption. With its logarithmic time complexity of O(log n), a recursive binary search is an essential tool in any programmer’s arsenal when dealing with large datasets and efficient searching.