This week's book giveaway is in the OCP forum.We're giving away four copies of OCP Java SE 8 Programmer II Exam Study Guide and have Kathy Sierra, Bert Bates, & Elizabeth Robson on-line!See this thread for details.
Win a copy of OCP Java SE 8 Programmer II Exam Study Guide this week in the OCP forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Recursive Binary Search Question

Ranch Hand
Posts: 36
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:
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!

Greenhorn
Posts: 9
• 1

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 :

Bartender
Posts: 10575
66
• 1

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: 36
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.

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 :

Bartender
Posts: 1558
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.

 It is sorta covered in the JavaRanch Style Guide.