Saturday, April 22, 2017

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 in a huge list. For example, in order to search a number in a list of 1 million number will take around 210 comparisons compared to 1 million comparison required by the linear search algorithm. Only thing is that the list must be sorted before you can use 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 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 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 structure which can give better performance than binary search when it comes to searching a value e.g. a hash table provide O(1) search performance if you have the key. This is why it's extremely important to 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 algorithm e.g. Introduction to Algorithms by Thomas H. Cormen.

Btw, almost all programming language 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 version of this method to perform a binary search on byte, char, int, long, float, double or an array of reference data type.

 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 .NET Framework also provides an Array.BinarySearch method.



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, 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 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 which support random access e.g. index based structure like array or list. You should not use binary search algorithm with a linear data structure like linked list.

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

Java Program to implement binary search using recursion


Implementation of Binary Search Algorithm in Java

Here is our sample Java program to implement 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 then calls 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 which is part of API and accept 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 it's method signature is different. It returns the index of the target value if found in array and -1 if the value doesn't exist in the array.

Recursive Binary Search Algorithm in Java


In each step, this recursive method first checks if low is greater than high or not i.e. start index is higher than end index or not if it does then it return -1 and method finish 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 midpoint matches with the target value, if yes then we have found the position of target value and 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 midpoint or upper half if 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 to first read Grokking Algorithms By Aditya Bhargava, he explained recursion really well using nice diagrams.
Recursive Binary Search Algorithm in Java



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, this is two of the essential search algorithms you learn in your computer science class. The binary search tree data structure take advantage of this algorithm and arrange data in hierarchical structure, so that you can search any node in O(logN) time. Though, you must remember that in order to use binary search, you need a sorted list or array, so, you also need to consider cost of sorting when you consider using binary search algorithm in real world.

Further Reading
Algorithms and Data Structures - Part 1
Algorithms and Data Structures - Part 2

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 Bubble sort algorithm in Java? (tutorial)
  • What is the difference between Comparison and Non-Comparison based sorting algorithm? (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 with your friends and colleagues. If you have any suggestion or feedback then please drop a comment. If you want to learn more about data structure and algorithm, I suggest you to read a good book on data structure e.g. Data Structure and Algorithm May Easy by Narsimha Karumanchi. 

2 comments :

Anonymous said...

Hello,
I venture to guess instead of the following:
int mid = (low + high) / 2;
it's better to use something like
int mid = low + (high - low) / 2;
(or even better: low + (high - low) >> 1)
in order to prevent all the mess in case of an arrays having 2^32 elements.

Javin Paul said...

Hello @Anonymous, good thought, but can you elaborate more please?

Post a Comment