Recursive Binary Search Algorithm in Java - Example Tutorial

The binary search algorithm is one of the most famous search algorithms in computer science. It allows you to search a value in logarithmic time i.e. O(logN), which makes it ideal to search a number on a huge list. For example, in order to search a number in a list of 1 million numbers will take around 210 comparisons compared to 1 million comparisons required by the linear search algorithm. The only thing is that the list must be sorted before you can use a binary search algorithm and it must support index-based search. That's why binary search is often implemented using an array because doing a binary search with a linked list will not be fast because it doesn't provide index-based access i.e. O(1) access. You have to traverse to that element to read its value in the linked list which is O(n), effectively reducing the performance of binary search to a sequential search algorithm.

By the way, there are also some advanced data structures that can give better performance than binary search when it comes to searching a value e.g. a hash table provides O(1) search performance if you have the key. 

This is why it's extremely important to be familiar with a different data structure. If you don't know what is a hash table and how it works, I suggest you read a good book on data structure and algorithms like the Introduction to Algorithms by Thomas H. Cormen, the gold standard for learning algorithms. 

Btw, almost all programming languages and libraries provide an implementation of binary search algorithm e.g. Java has Arrays.binarySearch() method to search an element in an array. JDK has several overloaded versions of this method to perform a binary search on byte, char, int, long, float, double, or an array of the reference data types.

 C++’s Standard Template Library(STL) also provides the implementation of binary search algorithms in binary_search and equal_range, depending exactly on what you need to do. Similarly, the .NET Framework also provides an Array.BinarySearch method.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

How does Binary Search Algorithm Work?

As per Wikipedia,  "A binary search or half-interval search algorithm finds the position of a specified value (the input "key") within a sorted array". In each step, the algorithm compares the input key-value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned.

Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. 

If the remaining array to be searched is reduced to zero, then the key cannot be found in the array, and a special "Not found" indication is returned.

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new array. Typically the array's size is adjusted by manipulating a beginning and ending index. 

The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass, hence its time complexity is O(logN) in both average and worst case.

Important points of Binary Search Algorithm

1) The Binary search algorithm, both iterative and recursive requires a sorted array. You can sort the array in your method, or can ask the client to sort that.

2) In the best case, the binary search algorithm will give the performance of order O(1), while in worst-case performance would be O(log n) because it essentially divides the array in half with each iteration or recursion.

3) Unlike linear search, which is not suitable for large arrays, a binary search can be efficient with even large collections, because of its log(n) performance.

4) Since binary search requires direct access to the element, it can only be applied to data structures that support random access like index-based structures like arrays or lists. You should not use a binary search algorithm with a linear data structure like a linked list.

5) If you need to use a binary search algorithm in your program then you should use Arrays.binarySearch() method instead of writing your own. It's always better to use the library method because it is well tested and generally provides better performance. This is also one of the pieces of advice I learned from Effective Java.

Implementation of Binary Search Algorithm in Java

Here is our sample Java program to implement a binary search algorithm using recursion in Java. The algorithm is naturally recursive because in every step it divides the input in half and then applies the same algorithm in the remaining half.  We have a public binarySearch(int[] input, int target) method which accepts an integer array and a target value to search in the array.

This method is then called another helper method which performs the binary search algorithm using recursion. This helper method is private and not visible to clients because it also accepts some additional variables in terms of start and end points to search in the array. 

This is why I have a public method that is part of API and accepts input and target value from a client and this private method is part of implementation hence not visible to the client.

This binarySearch() is the overloaded version of the previous one because its method signature is different. It returns the index of the target value is found in the array and -1 if the value doesn't exist in the array.

In each step, this recursive method first checks if low is greater than high or not i.e. start index is higher than the end index or not if it does then it returns -1, and the method finishes execution. This is the base case of the recursive binary search algorithm. 

If this condition is not met then it calculates the midpoint and checks if the value at the midpoint matches with the target value, if yes then we have found the position of the target value and the method completes by returning the index of the target value.

If the value is not found then a recursive call is made to the relevant half e.g.lower half if the target value is less than the value at the midpoint or the upper half of the target value is more than the value at the midpoint. 

By the way, if you have trouble understanding how a recursive algorithm works, I suggest you first read Grokking Algorithms By Aditya Bhargava, he explained recursion really well using nice diagrams.

Java Program to Implement Binary Search Algorithm

import java.util.Arrays;
import java.util.Scanner;
 
/**
* Java program to implement Binary Search using recursion. In order to write
* recursive binary search algorithm, you probably need two methods, one public
* API which accept array and number to be searched, and one private method to
* implement binary search algorithm using recursion.
*
* @author Javin
*/
public class RecursiveBinarySearch {
 
    public static void main(String args[]) {
 
        int[] sortedArray = new int[]{21, 41, 31, 12, 623, 543, 731, 1898};
        Arrays.sort(sortedArray);
 
        System.out.printf("Searching %d using binary search algorithm in %s %n",
                           31, Arrays.toString(sortedArray));
        binarySearch(sortedArray, 31);
 
        System.out.printf("Finding %d in %s by using recursive binary search 
                           algorithm  %n",
                           37, Arrays.toString(sortedArray));
        binarySearch(sortedArray, 37);
 
        System.out.printf("looking %d in array %s by binary search using 
                           recursion %n",
                          623, Arrays.toString(sortedArray));
        binarySearch(sortedArray, 623);
 
        System.out.printf("Binary Search %d in sorted array %s %n", 1898, 
                          Arrays.toString(sortedArray));
        binarySearch(sortedArray, 1898);
 
    }
 
    /**
     * Binary Search in Java using recursion, Calls a helper method to
     * implement binary search algorithm recursively.
     *
     * @param input
     * @param number
     * @return location of element in array
     */
    public static void binarySearch(int[] input, int number) {
        int index = binarySearch(input, number, 0, input.length - 1);
        if (index != -1) {
            System.out.printf("Number %d found at index %d %n", number, index);
        } else {
            System.out.printf("Sorry, number %d not found in array %n", number,
                        index);
        }
    }
 
    /**
     * helper method to implement binary search algorithm recursively. Require
     * extra low and high parameters to narrow search space.
     *
     * @param array - array which contains numbers
     * @param search - number to be searched
     * @param low
     * @param high
     * @return index of search item, or -1 if item is not found in array
     */
    private static int binarySearch(int[] array, int search, int low, int high) {
        //base case
        if (low > high) {
            return -1;
        }
 
        int mid = (low + high) / 2;
 
        // core logic is same as iterative algorithm
        if (array[mid] == search) {
            return mid;
        } else if (array[mid] < search) {
            return binarySearch(array, search, mid + 1, high);
        } else {
            // last possibility: a[mid] > x
            return binarySearch(array, search, low, mid - 1);
        }
    }
}
 
Output
Searching 31 using binary search algorithm in [12, 21, 31, 41, 543, 623, 
731, 1898]
Number 31 found at index 2
Finding 37 in [12, 21, 31, 41, 543, 623, 731, 1898] by using recursive 
binary search algorithm 
Sorry, number 37 not found in array
looking 623 in array [12, 21, 31, 41, 543, 623, 731, 1898] by binary search
 using recursion
Number 623 found at index 5
Binary Search 1898 in sorted array [12, 21, 31, 41, 543, 623, 731, 1898]
Number 1898 found at index 7

That's all about how to implement binary search using recursion in Java. Along with Linear search, these are two of the essential search algorithms you learn in your computer science class. The binary search tree data structure takes advantage of this algorithm and arranges data in a hierarchical structure so that you can search any node in O(logN) time. 

However, you must remember that in order to use binary search, you need a sorted list or array, so, you also need to consider the cost of sorting when you consider using binary search algorithms in the real world.


Other Data Structure and Algorithms tutorials you may like

• How to implement Quicksort algorithm in place in Java? (tutorial)
• How to implement Binary Search Tree in Java? (solution)
• How to implement Quicksort algorithm without recursion? (tutorial)
• How to implement Insertion sort algorithm in Java? (tutorial)
• How to implement a Bubble sort algorithm in Java? (tutorial)
• Difference between Comparison and Non-Comparison based sorting algorithms? (answer)
• How to implement Bucket Sort in Java? (tutorial)
• How to implement Binary Search Algorithm without recursion in Java? (tutorial)

Thanks for reading this article. If you like this article then please share it with your friends and colleagues. If you have any suggestions or feedback then please drop a comment.

P. S. -  If you want to learn more about data structure and algorithms, I suggest you read a good book on data structure like the Data Structure and Algorithm May Easy by Narasimha Karumanchi or join one of these best free Data Structure and Algorithms courses to start with.