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 ≥
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
Time for Recursion
Otherwise, we’ll check and see if our
midValue is greater than our
midValue is greater than
selectedValue then we know that our value is somewhere between our
leftTail and our
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
midValue – 1, and our
We wrap our up our outer conditional by recursively calling the
You see, if our
midValue wasn’t equal to our
selectedValue nor greater than our
selectedValue, then it must be less than our
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
midValue – 1, our
rightTail, and finally our
Wrapping Up our
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
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
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.