1.
Recursive Binary Search Algorithm
2.
Pictorial Representation
3.
Implementation of Recursive Binary search in C
3.1.
C
3.2.
Output
4.
Implementation of Recursive Binary Search in Python
4.1.
Python
4.2.
Output
5.
Implementation of Recursive Binary Search in Java
5.1.
Java
5.2.
Output
5.3.
Time Complexity
5.4.
Space Complexity
6.
7.
8.
8.1.
What distinguishes recursive binary search from iterative binary search?
8.2.
What is a recursion example?
8.3.
What exactly is binary search?
8.4.
What is the space complexity of recursive binary search?
8.5.
Is binary search recursive or not?
9.
Conclusion
Last Updated: May 31, 2024
Easy

# Recursive Binary Search

Kanak Rana

Recursive binary search algorithm repeatedly divides the search interval in half. It's implemented recursively, it reduce the time complexity significantly compared to linear search. This algorithm is efficient for sorted arrays or lists.

Recursive algorithms are used in binary search. The broad strategy is to look at the middle item on the list. The procedure is either terminated (key found), the left half of the list is searched recursively, or the right half of the list is searched recursively, depending on the value of the middle element.

Example: Input: arr[] = {1, 4, 3, 5, 6, 8, 11, 10, 14, 17}

Target value  = 8

OUTPUT: Element 8 is present at index 6.

## Recursive Binary Search Algorithm

1. Find the element at arr[size/2], which will be the array's midpoint. The array is split halfway, with the lower half consisting of items 0 to midpoint -1 and the top half consisting of elements midpoint to size -1.
2. Compare the key to arr[midpoint] by calling the user function.
3. If the key is a match, return arr[midpoint];
4. Otherwise return NULL, indicating that there is no match if the array has only one element.
5. Search the lower half of the array by repeatedly executing search if the key is less than the value taken from arr[midpoint].
6. Call search recursively to search the upper half of the array.

## Implementation of Recursive Binary search in C

• C

### C

#include <stdio.h>

// Recursive implementation of the binary search algorithm.
int binarySearch(int arr[], int low, int high, int number)
{
if (low > high)
{
return -1;
}

// Discovers the mid-point in the search space and compares it to the target
int mid = (low + high)/2;

// Base condition (target value is found)
if (number == arr[mid])
{
return mid;
}

// Remove all elements from the right search space, including the middle element.
else if (number < arr[mid])
{
return binarySearch(arr, low, mid - 1, number);
}

// Remove all elements from the left search space, including the middle element.
else
{
return binarySearch(arr, mid + 1, high, number);
}
}

int main(void)
{
int number;
int size; //array size
printf("Enter the value of arr size ");
scanf("%d",&size); // Input array size
int arr [size];
for(int i=0;i<size;i++)
{
printf("Enter array value\t");
scanf("%d",&arr[i]); // Input array value
}
printf("Enter the target value: ");
scanf("%d", &number);

int n = sizeof(arr)/sizeof(arr[0]);

int low = 0, high = n - 1;
int index = binarySearch(arr, low, high, number);
if (index != -1)
{
printf("Element found at index %d", index);
}
else
{
}
return 0;
}

## Implementation of Recursive Binary Search in Python

• Python

### Python

# Recursive implementation of the binary search algorithm
def binarySearch(arr, left, right, number):

# The starting point (search space is exhausted).
if left > right:
return -1

# Discovers the mid-point in the search space and compares it to the target
mid = (left + right) // 2

# Overflow can happen. Use below
# mid = left + (right-left) / 2

# Base condition (a target is found)
if number == arr[mid]:
return mid

# Remove all elements from the right search space, including the middle element.
elif number < arr[mid]:
return binarySearch(arr, left, mid - 1, number)

# Remove all elements from the left search space, including the middle element.
else:
return binarySearch(arr, mid + 1, right, number)

arr = []
n = int(input('Enter the value of array size '))
for i in range(0,n):
temp = int(input('Enter array value '))
arr.append(temp)
number = int(input('Enter the target value '))

(left, right) = (0, len(arr) - 1)
index = binarySearch(arr, left, right, number)

if index != -1:
print('Element found at index', index)
else:

### Output

Must Read Recursion in Data Structure

## Implementation of Recursive Binary Search in Java

• Java

### Java

import java.util.Scanner;
class Main
{
public static int binarySearch(int[] arr, int left, int right, int number)
{
if (left > right)
{
return -1;
}

// Discovers the mid-point in the search space and compares it to the target.
int mid = (left + right) / 2;

// Overflow can happen. Use below
// int mid = left + (right-left) / 2;

// Base condition (a target is found)
if (number == arr[mid])
{
return mid;
}

// Remove all elements from the right search space, including the middle element.
else if (number < arr[mid])
{
return binarySearch(arr, left, mid - 1, number);
}

// Remove all elements from the left search space, including the middle element.
else
{
return binarySearch(arr, mid + 1, right, number);
}
}

public static void main(String[] args)
{
int n;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the value of arr size ");
n = sc.nextInt();

int[] arr = new int[n];
for(int i=0; i<n; i++)
{
System.out.print("Enter array value ");
arr[i]=sc.nextInt();
}
int number;
System.out.print("Enter the target value: ");
number = sc.nextInt();

int left = 0;
int right = arr.length - 1;

int index = binarySearch(arr, left, right, number);

if (index != -1)
{
System.out.println("Element found at index " + index);
}
else
{
}
}
}

### Time Complexity

The time Complexity of Recursive Binary Search is O(log n).

Explanation: Since the array is divided into two parts according to the mid calculated, and every time the low and high values is changing according to this. The elements are searched in each divided sub-array recursively.

### Space Complexity

The space Complexity of Recursive Binary Search is O(log n) because of the stack size.

Read More - Time Complexity of Sorting Algorithms

## Advantages of Recursive Binary Search

There are several advantages of using recursive binary search:

• It is easier to understand and implement for many programmers
• It requires less code than an iterative solution
• It naturally divides problems into smaller subproblems
• It is ideal for problems that inherently involve recursion

## Disadvantages of Recursive Binary Search

Along with the advantages, there are some disadvantages of using recursive binary search as well:

• It can lead to stack overflow errors for large datasets
• Recursive calls may be less efficient than iterative loops
• It is not always amenable to tail-call optimization
• It may not be suitable in environments with limited stack space or Recursion support

### What distinguishes recursive binary search from iterative binary search?

The main distinction between the iterative and recursive versions of Binary Search is the space complexity of the iterative version, which is O(n), as opposed to the recursive version's O(log n).

### What is a recursion example?

Factorial(6) is the same as  6*5*4*3*2*1, and factorial(3) is 3*2*1, serving as classic examples of recursion.

### What exactly is binary search?

A "divide and conquer" approach known as binary search requires sorting the starting array first. Because the technique divides the array into two halves, it is called a binary algorithm.QQ

### What is the space complexity of recursive binary search?

The space complexity of the binary search recursive algorithm is O(log N).

### Is binary search recursive or not?

Binary search can be implemented both recursively and iteratively. The code you provided earlier is a recursive implementation of the binary search algorithm. It uses a recursive function to divide the search space in half with each recursive call until it finds the target element or determines that it's not present in the array.

## Conclusion

In this blog, we have learned about the Recursive Binary Search. The blog includes programming as well.

If you found this blog has helped you enhance your knowledge, and if you want to learn more algorithms like the recursive binary search algorithm, check out our articles below:

Recommended problems -

Refer to our guided paths on Code 360 to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enrol in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations

Happy Coding!

Live masterclass