Hello guys, In thelast article, we have seen the iterative implementation of binary search in Java, and in this article, you will learn how to implement binary search using recursion. Recursion is an important topic for coding interviews but many programmers struggle to code recursive solutions. I will try to give you some tips to come up with recursive algorithms in this tutorial. In order to implement a recursive solution, you need to break the problem into sub-problems until you reach a base case where you know how to solve the problem like sorting an array with one element. Without a base case, your program will never terminate and it will eventually die by throwing theStackOverFlowError.

In the case of recursive binary search implementation, we calculate themiddle position by taking the start and end position and check if the target element is equal to the middle element or not.

If thetarget, the number of the element you are searching in an array is equal then our search is complete, butif the target is greater than the middlewe look at thesecond half of the array and if the target is less than the middle element then we look into the first half of array.

This is possible because inthe case of binary search the array is always sortedif it's not, you mustsort the array before conducting a binary search.

So, in each iteration, the value of start and end position changes like at first,start=0 andend=length-1 but then depending upon the value of the target element we move the pointer to the first or second half of the array.

This gives you the base case I mean,. since thearray is getting smaller and smaller in every iteration at one point it will limit to just one element and after that end will be less than the start.

At this point,you can stop the binary search because now you cannot divide the array further, which means the element doesn't exist in the array. Our solution returns -1 at this point in time.

Good knowledge of basic data structure and algorithms also helps to code recursive solutions as most of the linked list and tree-based problems can be solved using recursion. This means you should sharp your algorithms skills as and when possible. If you need a course, I highly recommend Data Structures and Algorithms: Deep Dive Using Java as examples are given in Java programming language which makes it easy to understand them.

Why Recursion? if you already have Iterative Solution?

Now, some of you might askwhy should we learn a recursive algorithm if you already know an iterative one? Well, there are many reasons to do it as if you are preparing for the job interview, you must know both solutions because the interviewer prefers candidates who are good at recursion.

Second,recursion is a tricky concept to master and it's in your best interest to learn and master it. There are many programmers who struggle to understand recursion and as per my experience, I have found programmers who understand recursion better are comparative good coders and programmers than those who don't understand a recursive solution or struggle to use recursion in code.

If you are one of them then I strongly suggest you join a comprehensive data structure course like Grokking the Coding Interview: Patterns for Coding Questions on Educative which also explains importing problem-solving techniques like Recursion and Dynamic programming.



If you prefer a book,Grokking Algorithms book by Aditya Bhargava is also a good resource to learn Recursion. It's a visually refreshing book that takes a different and more real-life approach to teach you problem-solving.

Java Program to Implement Binary Search using Recursion

Here is our complete Java solution to implement a recursive binary search. I have a public method recursiveBinarySearch(int[] input, int key), which takes an integer array and a number as a key which we need to search in the array. This method return index of the key if it is found in the array otherwise it returns-1 to indicate that the key doesn't exist in the array.

This method doesn't do anything except accepting parameters from the caller. It then calls the binarySearch(int[] array, int start, int end, int target) which actually performs the binary search.

I have made this method aprivate method because it's an internal method and should not be exposed to the client or public. This gives you an option to rather switch to a better or iterative algorithm without any change on the client-side because they will keep calling the publicrecursiveBinarySearch(int[] input, int key) method.

Now the recursive logic is very simple, we calculate the middle index by using the start and end parameters passed to this method, which 0 and length - 1 at the start.

After that, we retrieve the middle element and compare it with the key or target. If it's equal then we return the index otherwise, we repeat the binary search in the first half or second half of the array depending upon whether the key is smaller than the middle element or larger than the key.

To repeat the binary search, we call the same method with a new start and end parameter e.g. start becomesstart = middle + 1 if we are searching for the second half of array and end becomes end = middle - 1 if you are searching for the first half of the array. Since we are calling the samebinarySearch() method, this solution becomes recursive.

If you want to learn more about recursion and binary search algorithm, you can also join Algorithms and Data Structures - Part 1 and 2 on Pluralsight, one of the most recommended courses to learn Data structure and algorithms. Here is a diagram that nicely explains the recursive binary search algorithm I have described above:

Recursive Binary Search Implementation in Java

Here is our complete Java program to implement a recursive solution to the binary search problem. You can simply run this program from your IDE likeEclipse orIntellijIDEA or you can also run this from the command prompt using java command. Just copy the code and save it into BinarySearchRecursive.java file and then compile usingjavac command and run usingjavacommand.

import java.util.Scanner;/* * Java Program to implement binary search algorithm * using recursion */publicclassBinarySearchRecursive {publicstaticvoid main(String[] args) {     Scanner commandReader=new Scanner(System.in);System.out.println("Welcome to Java Program to perform                              binary search on int array");System.out.println("Enter total number of elements : ");intlength= commandReader.nextInt();int[]input=newint[length];System.out.printf("Enter %d integers %n",length);for (int i=0; i <length; i++) {input[i]= commandReader.nextInt();     }System.outprintln("Please enter number to be searched                           in array (sorted order)");int key= commandReader.nextInt();intindex= recursiveBinarySearch(input, key);if (index==-1) {System.out.printf("Sorry, %d is not found in array %n", key);     }else {System.out.printf("%d is found in array at index %d %n", key,index);     }    commandReader.close();  }/**  * Java method to perform recursive binary search. It accept an integer array  * and a number and return the index of number in the array. If number doesn't  * exists in array then it return -1  *   * @param input  * @param number  * @return index of given number in array or -1 if not found  */publicstaticint recursiveBinarySearch(int[]input,int key) {return binarySearch(input,0,input.length-1, key);  }/**  * internal method which implement recursive binary search algorithm  *   * @param array  * @param start  * @param end  * @param target  * @return index of target element or -1 if not found  */privatestaticint binarySearch(int[] array,intstart,int end,inttarget) {int middle= (start+ end)/2;if (end <start) {return-1;     }if (target== array[middle]) {return middle;     }elseif (target < array[middle]) {return binarySearch(array,start, middle-1,target);     }else {return binarySearch(array, middle+1, end,target);     }  }}OutputWelcome to Java Program to perform binary searchonint arrayEnter total number of elements:3Enter3 integers102030Pleaseenter number to be searchedin array (sorted order)3030 is foundin array atindex2 Welcome to Java Program to perform binary searchonint arrayEnter total number of elements:5Enter5 integers234873Pleaseenter number to be searchedin array (sorted order)44 is foundin array atindex2

That's all abouthow to do the binary search using Recursion in Java. If you did the iterative implementation you will notice that recursive binary search is much simpler than iterative one because the process is naturally recursive. We are repeating the same process again and again and at every iteration, the problem set becomes smaller and smaller, this is the key to the recursive problem.


OtherJava Programming exercises forBeginners

• How to calculate the average of all numbers of an array in Java? (program)
• How to implement Linear Search in Java? (solution)
• 50+ Data Structure and Algorithms Coding Problems  (list)
• How to reverse an array in place in Java? (solution)
• How to calculate the sum of all elements of an array in Java? (program)
• 10 Data Structure and Algorithms Courses to Crack Interviews (courses)
• How to remove duplicate elements from the array in Java? (solution)
• How to check if a String contains duplicate characters in Java? (solution)
• How to print Fibonacci series in Java (solution)
• 10 Data Structure and Algorithms Books Every Programmer Read (books)
• How to check if the given String is a palindrome or not in Java? (solution)
• How to reverse a String in place in Java? (solution)
• How to find the highest occurring word from a given file in Java? (solution)
• 20+ String Coding Problems from Interviews (questions)
• How to check if the given number is prime in Java (solution)
• How to check if a year is a leap year in Java? (solution)
• 10 Free Data Structure and Algorithms course for Programmers (courses)
• How to count vowels and consonants in a given String in Java? (solution)
• How to check if two given Strings are Anagram in Java? (solution)
• How to remove duplicate characters from String in Java? (solution)
• How to find all permutations of a given String in Java? (solution)
• How to reverse words in a given String in Java? (solution)
• How to calculate the Area of Triangle in Java? (program)
• How to check if two rectangles intersect with each other in Java? (solution)
• How to calculate the square root of a given number in Java? (solution)
• How to find if given Integer is Palindrome in Java? (solution)

P. S. -As I told you if you understand recursion but struggle to come up with a recursive solution reading Grokking Algorithms can help you a lot. There is also an online course calledRecursion on Educative which is focused on explaining Recursion in an easy way. You can also take a look at that.