Binary search Program using recursion

Problem statement:- Program for binary search using recursion.

Data requirement:-

   Input Data:-n, arr

  Output Data:-String Output

Program in C

Here is the source code of the C program for binary search using recursion.

Code:

#include<stdio.h>

int binary_search(int arr[], int start, int end, int Search_ele)

{

    int mid;

    if (start > end) {

        return -1;

    }

    mid = (start + end) / 2;

    if (arr[mid] == Search_ele) {

        return mid;

    }

    if (Search_ele < arr[mid]) {

        return (binary_search(arr, start, mid - 1, Search_ele));

    } else {

        return (binary_search(arr, mid + 1, end, Search_ele));

    }

}

int main()

{

    int n,j;

    printf("Enter your array size:");

    scanf("%d",&n);

    int arr[n];

    printf("Enter the Array Element:");

    for(j=0;j<n;j++)

    {

        scanf("%d",&arr[j]);

    }

    int Search_ele;

    printf("Enter the search element:");

    scanf("%d",&Search_ele);

    int pos=binary_search(arr, 0, n, Search_ele);

    if ( pos== -1) {

        printf("%d not found in array\n", Search_ele);

    } else {

        printf("%d found at arr[%d]\n", Search_ele, pos);

    }

    return 0;

}

Input/Output:

Enter your array size:5

Enter the Array Element:10 5 6 7 8

Enter the search element:6

6 found at arr[2]

Program in C++

Here is the source code of the C++ Program to Implement Binary search using recursion.

Code:

#include<iostream>

using namespace std;

int binary_search(int arr[], int start, int end, int Search_ele)

{

    int mid;

    if (start > end) {

        return -1;

    }

    mid = (start + end) / 2;

    if (arr[mid] == Search_ele) {

        return mid;

    }

    if (Search_ele < arr[mid]) {

        return (binary_search(arr, start, mid - 1, Search_ele));

    } else {

        return (binary_search(arr, mid + 1, end, Search_ele));

    }

}

int main()

{

    int n,j;

    cout<<"Enter your array size:";

    cin>>n;

    int arr[n];

    cout<<"Enter the Array Element:";

    for(j=0;j<n;j++)

    {

        cin>>arr[j];

    }

    int Search_ele;

    cout<<"Enter the search element:";

    cin>>Search_ele;

    int pos=binary_search(arr, 0, n, Search_ele);

    if ( pos== -1) {

        cout<<Search_ele<<" not found in array";

    } else {

        cout<<Search_ele<<" found at "<< "arr["<<pos<<"]";

    }

    return 0;

}

Input/Output:

Enter your array size:4

Enter the Array Element:8 91 3 5

Enter the search element:9

9 not found in array

Program in Java

Here is the source code of the Java Program to Implement Linear search using recursion.

Code:

import java.util.Scanner;

public class BinarySearchRecursion {

static int binary_search(int arr[], int start, int end, int Search_ele)

{

    int mid;

    if (start > end) {

        return -1;

    }

    mid = (start + end) / 2;

    if (arr[mid] == Search_ele) {

        return mid;

    }

    if (Search_ele < arr[mid]) {

        return (binary_search(arr, start, mid - 1, Search_ele));

    } else {

        return (binary_search(arr, mid + 1, end, Search_ele));

    }

}

public static void main(String[] args) {

Scanner cs=new Scanner(System.in);

int n,i;

System.out.println("Enter your Array Size:");

n=cs.nextInt();

int arr[]=new int[n];

System.out.println("Enter the Array Element:");

for(i=0;i<n;i++)

{

arr[i]=cs.nextInt();

}

System.out.println("Enter the search element:");

int Search_ele=cs.nextInt();

int pos=binary_search(arr, 0, n, Search_ele);

    if ( pos== -1)

System.out.println(Search_ele+" not found in array");

else

System.out.println(Search_ele+" found at "+"arr["+pos+"]");

cs.close();

}

}

Input/Output:

Enter your Array Size:

5

Enter the Array Element:

7 8 9 10 11

Enter the search element:

10

10 found at arr[3]

Program in Python

Here is the source code of the Python program for binary search using recursion.

Code:

def binary_search(arr, start, end, Search_ele):

    if(start>end):

        return -1

    mid=(int)((start+end)/2)

    if(arr[mid]==Search_ele):

        return mid

    if (Search_ele < arr[mid]):

        return (binary_search(arr, start, mid - 1, Search_ele))

    else:

        return (binary_search(arr, mid + 1, end, Search_ele))

arr=[]

n = int(input("Enter the size of the array: "))

print("Enter the Element of the array:")

for i in range(0,n):

    num = int(input())

    arr.append(num)

Search_ele=int(input("Enter the search element:"))

pos=binary_search(arr, 0, n, Search_ele)

if (pos== -1):

    print(Search_ele," not found in array")

else:

    print(Search_ele," found at ","arr[",pos,"]")

Input/Output:

Enter the size of the array: 4

Enter the Element of the array:

3

8

2

6

Enter the search element:2

2  found at  arr[ 2 ]

Most Recommend Questions:-

• Write a Program to Implement Linear search using recursion.

• Write a Program to Implement Binary Search using Without recursion.

• Write a Program to Implement Linear Search using Without recursion.

• Write a Program to find the factorial of a number using recursion.

•  Write a Program to find the sum of n natural numbers using recursion.

More Questions:-

C/C++/Java/Python Practice Question