Recursive Binary Search

#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;
}

You can also try this code with Online C Compiler

Run Code

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

You can also try this code with Online Python Compiler

Run Code

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");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code