Recursive Binary Search Algorithm

Share on facebook
Share on pinterest
Share on twitter
Share on linkedin

Recursive Binary Search Algorithm

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 it in Java.

We’ll also provide other implementations in other languages.

What is Binary Search?

Suppose you had a sorted array of elements.

Array for Binary Search Algorithm Showing Midpoint

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.

Animated representation of the binary search algorithm on a sorted array of values

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.

class BinarySearch {
}

Create the Method

Next we’ll create our method (we’ll name it binarySearchMethod) which takes four arguments:

  1.  A sorted array
  2.  3 integer variables
public class BinarySearch {
    int binarySearchMethod(int sortedArray[], int leftTail, int rightTail, int selectedValue){
        
    }
}

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:
    public class BinarySearch {
	int binarySearchMethod(int sortedArray[],
                           int leftTail, 
                           int rightTail, 	   
                           int selectedValue){
    	if(rightTail >= leftTail){
            int midValue = leftTail + (rightTail - 1) / 2;
		}
}

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

    public class BinarySearch {
	int binarySearchMethod(int sortedArray[], int leftTail, int rightTail, int selectedValue){
    	if(rightTail >= leftTail){
            int midValue = leftTail + (rightTail - 1) / 2;
            
            if (sortedArray[midValue] == selectedValue)
                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.

Animated representation of dropping the values to the right of the midpoint value in the binary search algorithm
    public class BinarySearch {
	int binarySearchMethod(int sortedArray[],
                           int leftTail,
                           int rightTail,
                           int selectedValue){
    	if(rightTail >= leftTail){
            int midValue = leftTail + (rightTail - 1) / 2;
            
            if (sortedArray[midValue] == selectedValue)
                return midValue;
                
            if (sortedArray[midValue] > selectedValue)
                return binarySearchMethod(sortedArray,
                                          leftTail,
                                          midValue - 1, 
                                          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.
    public class BinarySearch {
	int binarySearchMethod(int sortedArray[],
                           int leftTail,
                           int rightTail,
                           int selectedValue){
    	if(rightTail >= leftTail){
            int midValue = leftTail + (rightTail - 1) / 2;
            
            if (sortedArray[midValue] == selectedValue)
                return midValue;
                
            if (sortedArray[midValue] > selectedValue)
                return binarySearchMethod(sortedArray,
                                          leftTail,
                                          midValue - 1, 
                                          selectedValue);
		
        	return binarySearchMethod(sortedArray, 
                                      midValue + 1,
                                      rightTail,
                                      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.

    public class BinarySearch {
	int binarySearchMethod(int sortedArray[],
                           int leftTail,
                           int rightTail,
                           int selectedValue){
    	if(rightTail >= leftTail){
            int midValue = leftTail + (rightTail - 1) / 2;
            
            if (sortedArray[midValue] == selectedValue)
                return midValue;
                
            if (sortedArray[midValue] > selectedValue)
                return binarySearchMethod(sortedArray,
                                          leftTail,
                                          midValue - 1, 
                                          selectedValue);
		
        	return binarySearchMethod(sortedArray, 
                                      midValue + 1,
                                      rightTail,
                                      selectedValue);
		}
        return - 1;
	}
}

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.

    import static org.junit.jupiter.api.Assertions.*;

class BinarySearchTest {

    @org.junit.jupiter.api.Test
    void binarySearchMethod() {

       BinarySearch testSearch = new BinarySearch();
       int sortedArray[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
       int arrayLength = sortedArray.length;
       int testValue = 0;
       assertEquals(0, testSearch.binarySearchMethod(sortedArray,
                                                     0,
                                                     arrayLength - 1,
                                                     testValue));

    }
}
Binary Search Algorithm - All Unit Tests Passed

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.

public class BinarySearch {

    int binarySearchMethod(int sortedArray[],
                           int leftTail,
                           int rightTail,
                           int selectedValue){
        if(rightTail >= leftTail){
            int midValue = leftTail + (rightTail - 1) / 2;

            if (sortedArray[midValue] == selectedValue)
                return midValue;

            if (sortedArray[midValue] > selectedValue)
                return binarySearchMethod(sortedArray,
                                          leftTail,
                                          midValue - 1,
                                          selectedValue);

            return binarySearchMethod(sortedArray,
                                      midValue + 1,
                                      rightTail,
                                      selectedValue);
        }

        return -1;
    }

    public static void main(String[] args) {
        BinarySearch object = new BinarySearch();
        int sortedArray[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
        int arrayLength = sortedArray.length;
        int selectedValue = 2;
        int ourAnswer = object.binarySearchMethod(sortedArray,
                                                  0,
                                                  arrayLength - 1,
                                                  selectedValue);
        if (ourAnswer == -1)
            System.out.println("Value isn't in the array.");
        else
            System.out.println("Value found at index " + ourAnswer);
    }
}
def recursive_binary_search(sorted_array, left_tail, right_tail, selected_value):
    
    if right_tail >= left_tail:

        midvalue = left_tail + (right_tail - left_tail) / 2

        if sorted_array[midvalue] == selected_value:
            return midvalue

        elif sorted_array[midvalue] > selected_value:
            return recursive_binary_search(sorted_array, left_tail, midvalue - 1, selected_value)

        else:
            return recursive_binary_search(sorted_array, midvalue + 1, right_tail, selected_value)

    else:
        
        return -1


sorted_array = [2, 3, 4, 10, 40]
selected_value = 10


result = recursive_binary_search(sorted_array, 0, len(sorted_array) - 1, selected_value)

if result != -1:
    print "Selected value is present at index % d" % result
else:
    print "Selected value is not present in Sorted Array \n"

Having Fun?

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.

Tell us a bit about your Business

Fill in your details and we’ll get back to you in no time.