File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Recursive Binary Search Question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursive Binary Search Question" Watch "Recursive Binary Search Question" New topic
Author

Recursive Binary Search Question

Hans Hovan
Greenhorn

Joined: Mar 03, 2013
Posts: 29
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

Joined: Mar 03, 2013
Posts: 9
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

Joined: Mar 17, 2011
Posts: 7779
    
  21

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

Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Hans Hovan
Greenhorn

Joined: Mar 03, 2013
Posts: 29
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

Joined: Dec 08, 2010
Posts: 1506
    
    5

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.


Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursive Binary Search Question