# Binary Search

The last page covered some simple examples of recursion, which could have been coded with loops just as easily. In other cases, using recursion is considerably more 'natural' than using loops.

### The Algorithm

You are given an array sorted in increasing order and would like to find the location of number `n` in it. While you could just search through the array in order, the goal is to find an optimal algorithm that will find the number much faster. Think about what algorithm you would use, and then click on the button below.

### The Code

Now that we've described an algorithm, let's convert it to code. We start with an empty method body (Hover over the parameter names for a description):

```int binarySearch(int[] ar, int iMin, int iMax, int num){
//algorithm here
}```

Next, let's fill in each step of the algorithm in code:

Step 1 - Check the middle Number. Let's declare a variable `iMid` to store the middle index1:

``````int binarySearch(int[] ar, int iMin, int iMax, int num){
int iMid = (iMax+iMin) / 2;
if(ar[iMid] == num){
return iMid;
}
}
``````

The binarySearch will now work when `num` happens to be right in the middle! When we're not that lucky, we'll need step 2:

Step 2. - Otherwise, check the 'correct' half next. If the number at the midpoint is greater than `num`, we'll want to check the left-hand side of the array. We can call binarySearch again with adjusted indices:

``````    //...previous code

else if(ar[iMid]>num){
return binarySearch(ar, iMin, iMid-1, num);
}
``````

This will call binarySearch with the same minimum index, but a new maximum index which is right before the number we just checked. If that condition isn't true, that means `num` is to the right:

``````    else{
return binarySearch(ar, __, iMax, num);
}
``````

We now have a working binary search! To get to work we just pass in a sorted array, along with the minimum and maximum starting indices and the number we're looking for. For example:

``````int[] ar = {1,3,4,7,9,11,13};
int index = binarySearch(ar, 0, ar.length-1, 4);
System.out.println(index);
``````

This code will print out `2`, the index that `4` is located at.

Here's a diagram of a binary search in action: What happens:

1. The initial call starts searching from cell 0 to the last cell in the array
2. binarySearch sees that 7 (located at index 3) is bigger than 4, so it calls binarySearch on 0 to 2.
3. 3 is less than 4, so binary search moves up and finally finds 4.

### Finishing the Search

The search works, but there's one issue - what if the number isn't found in the array? There's nothing to stop the indices from 'passing' each other and the search will continue until there's a StackOverflow error.

So we need to add another base case that checks for this condition:

``````if(iMax < iMin){
return -1;
}
``````

this will return `-1` when the `iMax` passed `iMin`, which means the number isn't in the array (assuming it's sorted).

It's important to cover all "exit possibilities" so that the recursive function doesn't try going on forever.

The complete binarySearch is below. To see it visualized, click here.

``````int binarySearch(int[] ar, int iMin, int iMax, int num){
if(iMax < iMin){
return -1;
}
int iMid = (iMax+iMin)/2;
if(ar[iMid] == num){
return iMid;
}
else if(ar[iMid]>num){
return binarySearch(ar, iMin, iMid-1, num);
}
else{
return binarySearch(ar, iMid+1, iMax, num);
}
}
``````

1. This is the simplest way to find the middle number, though it won't work for very large integers in Java.

### Challenge

What value should be put in the blank above so the correct minimum index is passed to binarySearch?

Alternatively, you can try out Learneroo before signing up.

### Challenge

The method doStuff takes in one square number. Create a separate recursive method that returns the square root of a given number. Call that method from doStuff and return the answer to be printed out.

Do not use any built in methods for calculating the square-root and don't try searching through all the numbers. Instead, use a binary-style search to home in on the actual square root.

(To make it simpler, the input will just contain square numbers.)

Alternatively, you can try out Learneroo before signing up.

• #### Kevin Guevara

Why r.binarySearch?

• #### David

When clicking on the Raw I/O option under Input I see "8":

Input

8 <<<<No Square
25
81
225
841
1024
7056
36
144

Correct Output
5
9
15
29
32
84
6
12

• #### Learneroo

@David, the first number in raw input states how many cases there will be, it's not one of the actual cases.

• #### David

Awesome site this is!

• #### armands

how do i know what is desired number? Should I make anarray from 0 to a, than start at midle checking if that number to power 2is a?

• #### Learneroo

@armands, you don't actually need an array, but that's the right idea (see the hint).

• #### taha

Hi guys, i have written this code https://ideone.com/eFWUiZ its kind of bad, i know it , i suck at recursion but it was a bit logical for me i really don't know where i'm missing up

• #### Learneroo

See if you can keep it organized. If you don't have the right number, see if it's larger or smaller and call your recursive method accordingly. You don't want to have two methods calling each other since that's just confusing. Look over the provided code for binary search and see how to adjust it for the "square root search" problem.

• #### catypus

WOOOHOOO! Man I'm pleased with my implementation of binary search.

However, you see how I got the range for iMid and iMax?

I made a crude estimation there... that the square root of any number could certainly be within the range = a/2

• #### Learneroo

After solving the question here, you can click on the "Featured Answers" link (next to the hint button) to see a possible solution. The idea is to use the same technique as binary search, but in search of the square root (i.e. the number that multiplied by itself equals the original number).

• # Working answer. Refer after trying it out

``````public static int computeRoot(int mid,int a){
if(mid==1){
return 0;
}
if(mid*mid == a ){
``````