Java Program to Implement Binary Search Using Recursion

by

In this article we are going to see how we can implement a binary search using recursion by Java programming language.

Java Program to Implement Binary Search Using Recursion

The recursive search implementation uses recursion to break the sorted array into two parts and so on, breaking until the element is found( or we reach the end).

Let’s see the program to understand it clearly.

Method-1: Java Program to Implement Binary Search Using Recursion By Using Static Input Value

Approach:

  • Create an sorted array of integers.
  • Create a variable and store the item to search.
  • Pass the array and the search item to our user defined function and store the returned index.
  • The user defined function takes the array, left and right indices and the search item as parameter. Then compare the middle element with the item. If the item is smaller, take the left part of the array, else the right part of the array and call the function on it.
  • Print the result.

Program:

import java.util.*;
// Main class
public class Main
{
   // Recursive Binary Search
   public static int binarySearch(int arr[], int left, int right, int item)
   {
       // Check for overflow first
       if (right >= left && left <= arr.length - 1) 
       {
           // Mid is the value located in the middle
           // between the left and right indices
           int mid = left + (right - left) / 2;
           // Check if the item is at middle position
           if (arr[mid] == item)
               return mid;
           // If the item is smaller than mid
           if (arr[mid] > item)
               return binarySearch(arr, left, mid - 1, item);
           // Else if the item is larger than mid
           return binarySearch(arr, mid + 1, right, item);
        }
       // If the element is not found
       return -1;
   }

   public static void main(String[] args)
   {
       // Array to search from
       int arr[] = {10,20,25,30,40,50};
       // Item to check for in the array
       int item = 25;
       // res stores the index returned from the recursive method
       int res = binarySearch(arr,0,arr.length-1,item);
       // Print the result
       if(res == -1)
           System.out.println("The element is not found");
       else
           System.out.println("The element is at index "+res);
    }
}

Output:

The element is at index 2

Method-2: Java Program to Implement Binary Search Using Recursion By Using User Input Value

Approach:

  • Ask the user to enter the number of elements and insert the elements next.
  • Then ask the user to search for an item inside.
  • Pass the array and the search item to our user defined function and store the returned index.
  • The user defined function takes the array, left and right indices and the search item as parameter. Then compare the middle element with the item. If the item is smaller, take the left part of the array, else the right part of the array and call the function on it.
  • Print the result.

Program:

import java.util.*;
// Main class
public class Main
{
   // Recursive Binary Search
   public static int binarySearch(int arr[], int left, int right, int item)
   {
       // Check for overflow first
       if (right >= left && left <= arr.length - 1)
       {
           // Mid is the value located in the middle
           // between the left and right indices
           int mid = left + (right - left) / 2;
           // Check if the item is at middle position
           if (arr[mid] == item)
               return mid;
           // If the item is smaller than mid
           if (arr[mid] > item)
               return binarySearch(arr, left, mid - 1, item);
           // Else if the item is larger than mid
           return binarySearch(arr, mid + 1, right, item);
        }
       // If the element is not found
       return -1;
    }

   public static void main(String[] args)
   {
       // Take user input
       Scanner sc = new Scanner(System.in);
       // Ask the user to enter array size
       System.out.print("Enter array size - ");
       int n = sc.nextInt();
       int arr[] = new int[n];
       // Ask the user to enter the array elements
       System.out.print("Enter the array elements - ");
       for(int i =0;i<n;i++)
           arr[i] = sc.nextInt();
       // Ask the user to enter an element to search
       System.out.println("Enter element to search for");
       int item = sc.nextInt();
       // res stores the index returned from the recursive method
       int res = binarySearch(arr,0,n-1,item);
       // Print the result
       if(res == -1)
           System.out.println("The element is not found");
       else
           System.out.println("The element is at index "+res);
    }
}

Output:

Enter array size - 5
Enter the array elements - 10 20 30 40 50
Enter element to search for
55
The element is not found

Don’t stop learning now. Get hold of all the important Java fundamentals with the Simple java program example guide and practice well.