Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

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.

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.

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.

Compare the key to arr[midpoint] by calling the user function.

If the key is a match, return arr[midpoint];

Otherwise return NULL, indicating that there is no match if the array has only one element.

Search the lower half of the array by repeatedly executing search if the key is less than the value taken from arr[midpoint].

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

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

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 '))

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

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.

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 Recursionsupport

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: