I'm trying to figure out a problem using recursion to find a binary number that the user enters. (I'm taking some Java classes and also trying to teach myself with online tools so I haven't got to anything too advanced yet...mostly if/else statement, loops, etc).
The main method gets the user's input and sets the range between 0-1000 (start, end) (I'm assuming the user enters a number in that range).
In the main method the recursion stats with:
search(num, start, end);
The output is supposed to look something like this:
Please enter a number:
Searching between 0 and 1000
Searching between 501 and 1000
Searching between 501 and 750
Searching between 626 and 750
Searching between 689 and 750
Searching between 720 and 750
I guess I'm not wrapping my head completely around how recursions work but I'd appreciate any help to send me in the right direction. I know I need to:
Calculate the mid point of the range. Compare the value to the mid point. If the value is equal to the mid point I print "Number found!". If the value is greater than the mid point I search the bigger half of the range (501-1000) and if smaller I search (0-500).
The code I have so far for search is below... I haven't really gotten too far yet because I'm lost. If the user enters a easily divisible number like 125 it will work but if its 50 or something it just goes into an infinite loop. Not even sure where to start with the 'if its greater than'. I think I might just be missing something simple here? Or maybe I have it completely set up wrong. Any help is appreciated. Thanks!
Hans Hovan wrote:I search the bigger half of the range (501-1000) and if smaller I search (0-500)...
Right, but in order for it to do that, your midpoint calculation needs to involve both start and end. Yours doesn't.
Another minor point: The first thing you check for is whether value equals midpoint, which is the least likely event to occur. This means that you almost always have to do at least 2 checks. In cases like this it's usually best to eliminate the most likely possibilities first.
However, it's simply a minor efficiency point, so don't sweat it. It makes no logical difference.
Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Joined: Mar 03, 2013
Thanks very much Michael. That did work. And thanks Winston for the tip as well.
I'm trying to understand exactly how though. I think I mostly get it. When you are having the method call itself in the last if/else statement and you are passing the value/start/midpoint or value/midpoint/end integer variables in are they taking the place of the integers (value/start/end) for that particular recursion step? Not sure if that makes sense...still trying to get the terminology down. Just trying to understand the 'why' of it.
Michael Novello wrote:Your line
else (value >= midpoint)
doesn't make sense. 'else' runs when all other conditions have failed. I think you mean to say
Hans Hovan wrote:I'm trying to understand exactly how though. I think I mostly get it. When you are having the method call itself in the last if/else statement and you are passing the value/start/midpoint or value/midpoint/end integer variables in are they taking the place of the integers (value/start/end) for that particular recursion step? Not sure if that makes sense...still trying to get the terminology down. Just trying to understand the 'why' of it.
Yes, it makes perfect sense
In this recursive algorithm what you are doing is:
1) Split the array in half
2) Check if middle element is same as what you are looking for. If it is same, print it and get out of procedure.
3) If middle element is bigger than your number, apply binarySearch on first half of array
4) Else (i.e. middle element is smaller than your number), apply binarySearch on second half of array
Thus, all you are doing is passing separate arguments during recursive calls. e.g. in step 3, original mid-point will be new end, and in step 4, original mid-point will be new start.