Results 1 to 3 of 3
Thread: Binary Search Problem
 02192009, 08:46 AM #1Member
 Join Date
 Feb 2009
 Posts
 2
 Rep Power
 0
Binary Search Problem
I'm trying to implement a binary search.
Here is my code:
Java 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; } }
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 my binarySearch method? I'm sure it's a small change but I just can't figure it out. :(
 02192009, 09:20 AM #2
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 26
On which loop you get the infinite loop? Did you find it, how can you make a conclusion on that?
 02192009, 10:22 AM #3Member
 Join Date
 Feb 2009
 Posts
 2
 Rep Power
 0
the dowhile loop runs forever.
it does this because it gets to a point where low = middle and high = low + 1
so low is perpetually less than high and the if statement keeps evaluating as true because the middle value is equal to the key so it never gets around to modifying the 'high' variable
i can't see a way to modify the code to fix this.
other than changing the while condition to (low < high  1) and when returning a value doing a comparison of middle to high and if they are unequal doing another "test" on the high value.
this is what i'm doing but it seems ugly to me. seems like i could modify my while statement or some of my assignments and not have to do the extra tests.
if anyone can figure out a way to do this, i'd greatly appreciate it.
i'm still O(lg(n)) but i like to have clean logical code.Last edited by sharpnova; 02192009 at 11:10 AM.
Similar Threads

Binary Search Tree
By michael_mke in forum New To JavaReplies: 3Last Post: 12042008, 02:03 AM 
Help. Binary Search Problem
By Krooger in forum Advanced JavaReplies: 1Last Post: 11032008, 06:19 AM 
Binary Search in Java
By Java Tip in forum AlgorithmsReplies: 0Last Post: 04152008, 07:43 PM 
binary search
By tranceluv in forum New To JavaReplies: 10Last Post: 01142008, 07:13 PM 
problem with recursive binary search program
By imran_khan in forum New To JavaReplies: 3Last Post: 08022007, 03:08 PM
Bookmarks