Binary Search Problem

I'm trying to implement a binary search.

Here is my code:

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 my binarySearch method? I'm sure it's a small change but I just can't figure it out. :(

On which loop you get the infinite loop? Did you find it, how can you make a conclusion on that?

Quote:

---

Originally Posted by Eranga

On which loop you get the infinite loop? Did you find it, how can you make a conclusion on that?

---

the do-while 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.