The binary search is one of the first algorithms computer science students learn.
Below we're going to discuss how the binary search algorithm works and go into detail about how to implement the recursive binary search algorithm in Java — we'll provide an implementation for Python as well.
What is Binary Search?
Suppose you had a sorted array of elements.
Now suppose you needed to be able to find a particular element within that array.
One way to do it would be to go through each element one at a time starting from the beginning (or the end), this method is called linear search.
Linear search has a time complexity of O(n), which means the time it will take is proportional to the value of n.
With binary search we select a value at the center of a sorted array, figure out if our value is greater or lower than our selected value, and then drop off whichever half our value isn't a part of.
What is the Time Complexity of Binary Search?
Taking this approach we reduce the time complexity to O(Log n).
Recursive Implementation of Binary Search in Java
Declare a Class
We'll start by declaring a class and giving it a name of BinarySearch.
Create the Method
Next we'll create our method (we'll name it binarySearchMethod) which takes four arguments:
- A sorted array
- 3 integer variables
leftTail represents the value at index 0 of our array. This should be the smallest value in the array.
rightTail should be the last value in the array (array.length - 1).
selectedValue is the value we're actually looking for.
Body of the Method
Within our body we'll start with our outer conditional, which checks whether or not the rightTail is ≥ leftTail.
If it is, then we create a middle value (e.g., midValue) that will be equal to half the value of the leftTail plus the value of our rightTail – 1.
Okay, that may be a bit confusing so let's write it out:
Within our conditional we have more conditions though!
We'll check to see if our midValue is equal to our selectedValue and if it is, great, we can stop checking because we've found our answer (e.g., return midValue).
Time for Recursion
Otherwise, we'll check and see if our midValue is greater than our selectedValue.
If midValue is greater than selectedValue then we know that our value is somewhere between our leftTail and our midValue, right?
So we can now drop off all of the values greater than our midValue.
This is where our first bit of recursion occurs.
To do this we'll call our binarySearchMethod again and pass to it our sortedArray, our leftTail, our midValue – 1, and our selectedValue.
Déjà Vu
We wrap our up our outer conditional by recursively calling the binarySearchMethod again.
You see, if our midValue wasn't equal to our selectedValue nor greater than our selectedValue, then it must be less than our selectedValue.
In which case we drop all values to the left our of midValue and begin again.
So we'll call our binarySearchMethod and pass to it our sortedArray, our leftTail becomes midValue – 1, our rightTail, and finally our selectedValue.
Wrapping Up our binarySearchMethod
Now we wrap up our binarySearchMethod by terminating it. To do this we can return – 1.
If we don't…well, we'll get a compilation error due to a missing return statement.
Let's Test Our Method
Unit Testing
We can test our method in a variety of ways. We'll test it using unit tests.
We'll cover how to create unit tests in a later post, but for now, see below.
Test Using System.out.println
You can also run some tests by calling the method and returning output to the print line. See below for the full implementation.
Complete Recursive Binary Search Algorithm in Java
Recursive Binary Search in Python
Keep Learning
I hope this resource helped you understand the Binary Search algorithm. If you have any questions or suggestions, feel free to drop us an email. We would be glad to receive the input.
If you're feeling up to it, you can learn a bit more about the binary search algorithm by visiting the very well written Wikipedia page article on it.