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.
This task is similar to the "guess-a-number" game where one person guesses a number and is told if the correct number is higher or lower. The goal is to repeatedly split the possible numbers in half until you reach the correct number.
- Check the middle of the given numbers, and see if it's the right number. Return that index if it's right, and otherwise continue.
- If the number is higher than
n
, check the left side (of the number checked) in the same way. If the number is lower thann
, check the right side.
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:
- The initial call starts searching from cell 0 to the last cell in the array
- binarySearch sees that 7 (located at index 3) is bigger than 4, so it calls binarySearch on 0 to 2.
- 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?
Please sign in or sign up to submit answers.
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.)
Please sign in or sign up to submit answers.
Alternatively, you can try out Learneroo before signing up.
Comments
Kevin Guevara
Jun 1, 4:50 PMWhy r.binarySearch?
David
Jun 12, 1:37 PMDear admin,
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
Your Output (I still have not solved it, so currently empty)
But on the instructions it is mentioned "(To make it simpler, the input will just contain square numbers.)" Is this a typo on the Raw I/O or is it actually handling that? Because on one of my tests i got Stack Overflow so currently not sure if expected...
Thanks in advance,
David.
Learneroo
Jun 12, 1:43 PM@David, the first number in raw input states how many cases there will be, it's not one of the actual cases.
David
Jun 13, 9:51 PMAwesome site this is!
armands
Jun 21, 7:21 AMhow 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
Jun 21, 10:28 PM@armands, you don't actually need an array, but that's the right idea (see the hint).
taha
Jul 12, 12:05 PMHi 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
Jul 31, 4:10 PMSee 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.
(PS - You can link to your learneroo code submission, no need to link elsewhere.)
catypus
Jul 4, 3:24 AMWOOOHOOO! 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
But thats not very efficient. How do I choose a smaller range and thus use less cycles on finding the square root?
Learneroo
Jul 4, 2:54 PMAfter 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).
Binoy
Oct 23, 3:08 AMWorking answer. Refer after trying it out