Results 1 to 3 of 3
  1. #1
    sharpnova is offline Member
    Join Date
    Feb 2009
    Posts
    2
    Rep Power
    0

    Default 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;
            }
    }
    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. :(

  2. #2
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

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

  3. #3
    sharpnova is offline Member
    Join Date
    Feb 2009
    Posts
    2
    Rep Power
    0

    Default

    Quote Originally Posted by Eranga View Post
    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.
    Last edited by sharpnova; 02-19-2009 at 11:10 AM.

Similar Threads

  1. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 02:03 AM
  2. Help. Binary Search Problem
    By Krooger in forum Advanced Java
    Replies: 1
    Last Post: 11-03-2008, 06:19 AM
  3. Binary Search in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:43 PM
  4. binary search
    By tranceluv in forum New To Java
    Replies: 10
    Last Post: 01-14-2008, 07:13 PM
  5. problem with recursive binary search program
    By imran_khan in forum New To Java
    Replies: 3
    Last Post: 08-02-2007, 03:08 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •