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.
- Java Program to Implement Binary Search Using Recursion By Using Static Input Value
- Java Program to Implement Binary Search Using Recursion By Using User Input Value
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.