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.

####

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:

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);

}

}

}

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

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.

####
**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:

**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