Binary Search using Recursion in Java

In the last 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. In order to implement a recursive solution, you need a base case because without a base case your program will never terminate and it will eventually die by throwing StackOverFlowError . In the case of recursive binary search implementation, we calculate middle position by taking start and end position and check if the target element is equal to the middle element or not. If target, the number of element you are searching in an array is equal then our search is complete, but if the target is greater than middle we look on second half of array and if the target is less than middle element then we look into the first half of array. This is possible because in the case of binary search the array is always sorted, if it's not, you must sort the array before conducting a binary search.


So, in each iteration, the value of start and end position changes e.g. at first, start=0 and end=length-1 but then depending upon the value of target element we move the pointer to first or second half of array. This gives you the base case i.e. since the array 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 element doesn't exist in the array. Our solution return -1 at this point of time.



Now, some of you might ask why should we learn a recursive algorithm if you already know an iterative one? Well, there are many reasons to do it e.g. if you are preparing for the job interview, you must know both solutions because 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 coder and programmer 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 read a new algorithm book called Grokking Algorithm by Aditya Bhargava. It's a refreshing book which takes a different and more real life approach to teaching you algorithms.

Recursive binary search in Java


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 key which we need to search in the array. This method return index of key if it is found in array otherwise it return -1 to indicate that key doesn't exists in 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 a private method because it's an internal method and should not be exposed to 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 be keep calling the public recursiveBinarySearch(int[] input, int key) method.

Now the recursive logic is very simple, we calculate middle index by using start and end parameter passed to this method, which 0 and length - 1 at the start. After that, we retrieve 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 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 becomes start = middle + 1 if we are searching for second half of array and end becomes end = middle - 1 if you are searching for first half of the array. Since we are calling the same binarySearch() method, this solution becomes recursive.  If you want to learn more about recursion and binary search algorithm, you can also read Introduction to Algorithms, one of the most recommended books to learn Data structure and algorithms.

Here is a diagram which nicely explains the recursive binary search algorithm I have described above:

Binary Search using Recursion in Java



Recursive Binary Search Implementation in Java

import java.util.Scanner;

/*
 * Java Program to implement binary search algorithm
 * using recursion
 */

public class BinarySearchRecursive {

  public static void 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 : ");
  int length = commandReader.nextInt();
  int[] input = new int[length];

  System.out.printf("Enter %d integers %n", length);
  for (int i = 0; i < length; i++) {
  input[i] = commandReader.nextInt();
  }

  System.out
  .println("Please enter number to be searched in array (sorted order)");
  int key = commandReader.nextInt();

  int index = 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
  */
  public static int 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
  */
  private static int binarySearch(int[] array, int start, int end, int target) {
  int middle = (start + end) / 2;
  if (end < start) {
  return -1;
  }

  if (target == array[middle]) {
  return middle;
  } else if (target < array[middle]) {
  return binarySearch(array, start, middle - 1, target);
  } else {
  return binarySearch(array, middle + 1, end, target);
  }
  }

}

Output
Welcome to Java Program to perform binary search on int array
Enter total number of elements : 
3
Enter 3 integers 
10
20
30
Please enter number to be searched in array (sorted order)
30
30 is found in array at index 2 

Welcome to Java Program to perform binary search on int array
Enter total number of elements : 
5
Enter 5 integers 
2
3
4
87
3
Please enter number to be searched in array (sorted order)
4
4 is found in array at index 2 


That's all about how 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. As I told you, if you understand recursion but struggle to come up with recursive solution reading Grokking Algorithms can help you  a lot.


Other Java Programing exercises for Beginners
  • How to calculate the average of all numbers of an array in Java? (program)
  • How to implement Linear Search in Java? (solution)
  • How to reverse an array in place in Java? (solution)
  • How to calculate the sum of all elements of an array in Java? (program)
  • 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)
  • How to check if given String is 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)
  • How to check if given number is prime in Java (solution)
  • How to check if a year is a leap year in Java? (solution)
  • How to count vowels and consonants in 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 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)


Further Reading
If you are serious about building your data structure and algorithm skill and what to do well on programming job interviews on tech giants like Amazon, startups likes Uber, and Investment banks like Citibank, you should expand your knowledge by reading following books.:


No comments:

Post a Comment