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

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

}
}
``` ### 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;
0,
arrayLength - 1,
selectedValue);
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.