Write a Java program for binary search using recursion

Binary search using recursion in java is quite a tricky program. Binary search in java is a very simple program but when it comes to logic and programming practice let’s write Java code for binary search by using recursion.

For this, first, let us understand what is binary search and recursion.

What is Recursion?

A function calling itself is called recursion. For recursion, the function must have an exit condition.

Syntax:-

method_name()

{

    if(exit_condition) return;

    else return method_name();

}

What do you mean by Binary Search?

It is a search algorithm used to search an element from a sorted array. It keeps on dividing the array into two parts until the middle element is found to be equal to the item to be searched.

The complexity of the binary search algorithm

O(log n)

Example of binary search algorithm using recursion:

Input: Array = {1,3,5,7,9}

Find 9

Output: Item found at 4th index

Algorithm for binary search algorithm using recursion:-

1. Enter the no. of elements, array, and item to be searched from the user.

2. Create a method binarySearch() which takes the following parameters:-

the array
element to be searched
the first index of array
last index of the array

3. In the method, calculate the middle index of the array. Create a while loop that runs until the first index is less than the last index.

4. If the element to be searched is equal to the middle index element, return the index.

5. If the element to be searched is greater than the array middle index element, it means that we have to search in the right half of the array. We can do this by calling the method again by changing the first index to middle element+1. ( As the middle element is already checked for equality)

6. If the element to be searched is lesser than the array middle index element, it means that we have to search in the left half of the array. We can do this by calling the method again by changing the last index to middle element-1.

Java Program for Binary Search Algorithm Using Recursion

import java.util.Scanner;
public class Binary
{
    public static int binarySearch(int[] ar, int item, int first, int last)
    {
        int mid=(first+last)/2;
        while(first<=last)
        {
            if(ar[mid]==item) return mid;
            else if(ar[mid]>item) return binarySearch
            (ar,item,first,mid-1);
            else return binarySearch(ar,item,mid+1,last);
        }
        return -1;
    }
    public static void main(String[] args)
   {
        Scanner sc=new Scanner(System.in);
        System.out.println("Enter number of elemnts in array:");
        int n=sc.nextInt();
        int ar[]=new int[n];
       System.out.println("Enter array elements");
       for(int i=0;i<n;i++) ar[i]=sc.nextInt();
       System.out.println("Enter element to be searched");
       int item=sc.nextInt();
       int index=binarySearch(ar, item, 0, n-1);
       if(index==-1) System.out.println("Item not found");
       else System.out.println("Item found at index "+index);
    }
}