Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Recursive Binary Search
2.1.
Algorithm
3.
Pictorial Representation
4.
Implementation of Recursive Binary search in C
4.1.
C
4.2.
Output
5.
Implementation of Recursive Binary Search in Python
5.1.
Python
5.2.
Output
6.
Implementation of Recursive Binary Search in Java
6.1.
Java
6.2.
Output
6.3.
Time Complexity
6.4.
Space Complexity
7.
Advantages of Recursive Binary Search
8.
Disadvantages of Recursive Binary Search
9.
Frequently Asked Question 
9.1.
Q. What distinguishes recursive binary search from iterative binary search?
9.2.
Q. What is a recursion example?
9.3.
Q. What exactly is binary search?
9.4.
Q. What is the space complexity of recursive binary search?
9.5.
Q. Is binary search recursive or not?
10.
Conclusion
Last Updated: Mar 27, 2024
Easy

Recursive Binary Search

Author Kanak Rana
2 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

You must have read and known about Binary Search. A binary search is an effective way to find an element in a sorted list. While a basic search for a component can be completed in O(N) time, binary search accelerates the process to O (log N). For array-related issues, binary search is a great technique to have in mind.

Recursive Binary Search

Today we will look into the Recursive Binary Search and get into some details about it.

What is Recursive Binary Search

Define recursive binary search

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. 

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.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Pictorial Representation

Pictorial Representation Step 1
Pictorial Representation arrow
Pictorial Representation Step 2
Pictorial Representation arrow
Pictorial Representation step 3

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
{
printf("Element not found in the array");
}
return 0;
}

Output

output

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:
print('Element not found in the array')

Output

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
{
System.out.println("Element not found in the array");
}
}
}

Output

output

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

Frequently Asked Question 

Q. 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).

Q. 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.

Q. 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

Q. What is the space complexity of recursive binary search?

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

Q. 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 Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll 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! 

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass