Binary Search Problem

[sharpnova]

I'm trying to implement a binary search.

Here is my code:

import java.util.Scanner;
import java.io.*;

public class test3
{
        public static void main( String args[] )
        {
                System.out.println(binarySearch());
        }

        public static Boolean testMiddle(int middle)
        {
                int key = 37;
                if (middle <= key) return true;
                else return false;
        }

        public static int binarySearch()
        {
                int low=0;
                int high = 40;
                int middle = (low + high) / 2;
                do
                {
                        if (testMiddle(middle))
                        {
                                low = middle;
                                middle = (low + high) / 2;
                        }
                        else
                        {
                                high = middle;
                                middle = (low + high) / 2;
                        }
                } while (low<high);
                return middle;
        }
}

Just imagine that there is some unknown key. (in this case it happens to be 37)

And the binarySearch method has to keep making calls to testMiddle to "zero in" on the key.

If the argument to testMiddle is <= the key, then it returns true. if it's greater, then it returns false.


My binarySearch method has problems. it goes into infiniteloops sometimes.

How do I need to modify it?

[dlorde]

You want to stop the search when you've hit the target. Think about what happens when 'middle' equals 'key'.

All you have to do is step through the code by hand for 30 secs and you'll see. It's called debugging.

Testing can show the presence of errors, but not their absence...
E. Dijkstra

[sharpnova]

I have debugged. I've debugged to death. I can see the problem clearly but can't find a way around it.

The function only tells if you are "less than or equal to" or "greater than"

therefore there is no way to know when you've "hit" the target. You have to take the binary search all the way to the end.

It's extremely clear that you didn't read my question carefully at all.

Can anyone else help?

Thanks.

[ProgramThis]

Well, apparently you didn't debug good enough. dlorde has given you the answer but you refuse to accept it. What happens is this:

mid = 0 + 40 / 2 => 20

20 <= 37 --> true
low = 20
mid = 20 + 40 / 2 --> 30

30 <= 37 --> true
low = 30
mid = 30 + 40 / 2 --> 35

35 <= 37 --> true
low = 35
mid = 35 + 40 / 2 --> 37 (rounded of couse because of int)

37 <= 37 --> true
low = 37
mid = 37 + 40 / 2 --> 38

38 <= 37 --> false
high = 38
mid = 37 + 38 / 2 --> 37

37 <= 37 --> true
low = 37 (which it already did...)
mid = 37 + 38 / 2 --> 37

And here is where you get your infinite recursion. Mid will always be 37, low will always be 37, high will always be 38. Therefore your loop will never end.


So, before you post ignorant comments to the guy who has help the most people on this Java board for the last 10+ years you should try to do as he suggests. So clearly it is YOU who did not read HIS post.

You NEVER check to see if the number is exactly what you are looking for so you can terminate the loop. Which is exactly what dlorde said. All you check is for low > high which never happens in this case.

[_uj]

My binarySearch method has problems.

It's a very standard algorithm with lots of implementations posted on the internet, like here,

http://www.leepoint.net/notes-java/a...arysearch.html

Note (for future reference) that a binary search only works on sorted data.

[dlorde]

It's extremely clear that you didn't read my question carefully at all.

Your question was "How do I need to modify it?". I didn't answer that directly because I think it's better that you work out how to modify it yourself rather than being spoon-fed, so I pointed out what was wrong with the code so you could fix it.

The point is that your design needs to be reworked so that you can tell when you've hit the target.

I know it's frustrating to keep hacking at the code without a result, and with the code layout you've got, you're unlikely to fix your problem that way.

By now you should have a better understanding of the task than when you started, so I suggest going back to the drawing-board with what you know now, and working out, on paper, exactly what steps are needed to achieve the result, then go back to the computer and translate that into Java code.

If you don't find our responses to your question useful, then you can ask for clarification, rephrase the question, or just move on, but being rude will simply antagonise the people you're asking for help, which is not an effective way of getting answers.

We think too much about effective methods of teaching and not enough about effective methods of learning. No matter how good teaching may be, each student must take the responsibility for his own education...
J. Carolus S.J.

[sharpnova]

No. The frustrating thing is that as I said I already debugged everything. I was well aware in fact EXACTLY aware of what was causing the infinite loop. I should have been more clear about this. My mistake.

There wasn't even any need to trace it out. I knew 100% that the problem was caused by low = mid and high = low + 1 = mid + 1.

The problem is I can't figure out how to modify the search to fix the problem. Everytime I modify things by adding or subtracting 1 to the conditions or assignments it causes errors on different ends of the binary search.

Can't find a clean fix that patches up this problem. But as I said, yes I have debugged and I know what's causing the infinite loop. I'm just looking for a solution as to how to fix it.

Also, I appreciate the sentiment of trying to get me to figure out the solution myself but:

A. I'm not a student. this isn't homework
B. I've been hacking at this forever and if someone could just provide a solution it would relieve what feels like a century long headache.

[dlorde]

Like I said, I think you need to rework the design from scratch.

This is not a Java problem, it's a binary search logic problem. If you're stuck in a mental rut, do as _uj has suggested, and look at some working code examples for ideas. If all you need is some code, there's plenty out there. If you want to figure out why your design doesn't work, it's worth seeing how working binary searches do it.

I'm not going to try and fix the code you posted, because I don't think it's easily fixable in its present configuration.

That's just my opinion - there may be others who can see a simple fix.

No matter how far down the wrong road you have gone, turn back now...
Turkish Proverb

[_uj]

Also, I appreciate the sentiment of trying to get me to figure out the solution myself but:

A. I'm not a student. this isn't homework
B. I've been hacking at this forever and if someone could just provide a solution it would relieve what feels like a century long headache.

Just consult any standard textbook on algorithms & data structures, or search the internet (like the link I provided above).

A binary search isn't something you code yourself. It's a standard algorithm available in the standard libraries of most programming languages. Java has a binarySearch method both for Arrays and Collections. Don't reinvent the wheel.

[sharpnova]

I've done binary searches before. I'm familiar with the algorithm and all the complexity theory behind it.

It was just this implementation that was giving me a headache.

And no this was not a bad approach. It was a very logical approach. It was a minor fix.

I never claimed it was a Java problem.

Bottom line is no one could figure it out and you all came up with different excuses as to why. I found that amusing.

Thanks for jumping to the conclusions that I was incompetent before attempting the problem and seeing that it was just a subtle and interesting deviation from the normal binary search.

It turns out that when the query returns only <= or >, it alters the nature of binary search in a subtle and interesting way.

I'd educate you all in how this works, but you pretty much refused to help me in the slightest bit (unless you count condescending suggestions) so you will remain ignorant of the solution.

Headache gone. Relief sets in. Actually it was last night that this occurred. Now I'm just cleaning up the trash (you guys)

Tata. Oh btw.. gamedev was 1000X more helpful. They at least tried and failed.. instead of.. well.. as i said you guys probably did try and fail but you wouldn't admit you tried. Lol. Guess professionalism has been forgotten here.

[dlorde]

Glad you found your solution. We judged your post from the code you posted, which wasn't competent, and the problems you said you were having, which indicated a novice programmer. You didn't find our approach helpful and took your non-Java problem to a non-Java forum. Try not to be so bitter and ungracious - it says more about you than it does about anyone else.

One can think effectively only when one is willing to endure suspense and to undergo the trouble of searching...
J. Dewey

[_uj]

Tata. Oh btw.. gamedev was 1000X more helpful. They at least tried and failed.. instead of.. well.. as i said you guys probably did try and fail but you wouldn't admit you tried. Lol. Guess professionalism has been forgotten here.

Whining and blaming others for your shortcomings won't get you anywhere. Some people just aren't cut out to be programmers. They always end up struggling with trifles for days and weeks. For your own sake and others, maybe you should do something else.

[ProgramThis]

Not that this guy is likely to come back, but I just can't help myself...

I've done binary searches before. I'm familiar with the algorithm and all the complexity theory behind it.

[citation needed]

And no this was not a bad approach. It was a very logical approach. It was a minor fix.

Yes, yes it is a very bad approach. There was nothing "very logical" about it. You are:
a.) hard coding your high, your low and your search-for criteria
b.) don't have any checks for the actual number you are looking for! (how did you ever expect to get an answer?)
c.) You tried to abstract a simple check by creating an unnecessary method whose whole purpose is to perform a standard check that could easily be done inside of the 'if' statement. You thought that you were cleaver, but you weren't.

Bottom line is no one could figure it out and you all came up with different excuses as to why. I found that amusing.

I am pretty sure in my previous post that I demonstrated that I knew exactly what was going on in your program. Because I didn't give you the answer to your obvious entry level programming class problem doesn't mean that I didn't know it.

Thanks for jumping to the conclusions that I was incompetent before attempting the problem and seeing that it was just a subtle and interesting deviation from the normal binary search.

Your original question was:
"My binarySearch method has problems. it goes into infiniteloops sometimes.

How do I need to modify it?"
Dlorde and I demonstrated and explained to you exactly why it was going into infinite loops, we left it up to you to modify the code. _uj asked you why you were reinventing the wheel. He did so because this is NOT an interesting deviation from the normal search, but an ineffective uneducated version that did not work.

Look, it is obvious that you are a novice programmer and that you are either teaching yourself how to program or are in school. Don't try to pass yourself off as some intellectual guru that was stuck on a "difficult" or "interesting" problem, because it was neither.

[dlorde]

You could always PM him

You wonder why, if he'd "done binary searches before" and was "familiar with the algorithm and all the complexity theory behind it", he didn't use his earlier code instead of the rubbish he posted...

The greatest obstacle to discovery is not ignorance, but the illusion of knowledge...
D. Boorstin

[ProgramThis]

You could always PM him

Yeah, I never know when to keep quiet, just ask my wife

You wonder why, if he'd "done binary searches before" and was "familiar with the algorithm and all the complexity theory behind it", he didn't use his earlier code instead of the rubbish he posted...

I think that it was all bluster. Either he felt stupid for writing such crap and tried to defend himself, or he is one of those that considers everything they do to be perfection, even if it's crap.

The greatest obstacle to discovery is not ignorance, but the illusion of knowledge...
D. Boorstin

Random quote, or pulled out for this thread?