Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursive Binary Search Question

 
Hans Hovan
Ranch Hand
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:
735
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
Number found!

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!

 
Michael Novello
Greenhorn
Posts: 9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your line

else (value >= midpoint)

doesn't make sense. 'else' runs when all other conditions have failed. I think you mean to say

else if (value >= midpoint)

Try this :

 
Winston Gutkowski
Bartender
Pie
Posts: 10417
63
Eclipse IDE Hibernate Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.

Winston
 
Hans Hovan
Ranch Hand
Posts: 31
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

else if (value >= midpoint)

Try this :

 
Anayonkar Shivalkar
Bartender
Posts: 1557
5
Eclipse IDE Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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:

Procedure binarySearch:
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.

I hope this helps.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic