# Recursive Binary Search Question

Hans Hovan

Ranch Hand

Posts: 31

posted 3 years ago

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!

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

posted 3 years ago

Right, but in order for it to do that, your midpoint calculation needs to involve both

Another minor point: The first thing you check for is whether

However, it's simply a minor efficiency point, so don't sweat it. It makes no logical difference.

Winston

- 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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Hans Hovan

Ranch Hand

Posts: 31

posted 3 years ago

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.

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 :

posted 3 years ago

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.

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)