Java - recursive binary search help

Question

The following code is how I'm trying to create a recursive binary method..

public static int binarySearch(Comparable[] objArray, Comparable item)
{

    int lower=0;
    int upper=objArray.length -1;
    int i = -1;
    int compareResult;
    boolean found = false;
    while ((lower<=upper) && (!found))
    {
        i=(lower+upper)/2;
        compareResult=item.compareTo(objArray[i]);
        if(compareResult<0)
        {
            upper=i-1;
        }
        else
            if (compareResult>0)
            {
                lower=i+1;
            }
            else
            {
                found=true;
            }


    }
    return compareResult;



}

I feel as thought I'm not doing this correctly...any suggestions?

-D

Err, with recursion, you call the method itself within the method... I don't see you do that. — Bart Kiers
– Bart Kiers, Commented Nov 15, 2010 at 19:31
Suppose that you only have one item in your array. Then lower==upper and you will never enter the while loop. — Nathan S.
– Nathan S., Commented Nov 15, 2010 at 19:33
I like how you return the compareResult instead of the index. — Kyle P
– Kyle P, Commented Nov 15, 2010 at 20:05

Brendan · Accepted Answer · 2010-11-15 19:41:57Z

1

You are using a loop. In order for your method to be recursive, it needs to call itself until it reaches some breaking condition.

Check out Wikipedia's example.

Essentially, your "while" condition will be the condition that breaks your recursion (i.e. stops the method from calling itself), and the contents of your current loop will instead be setting up the "upper" and "lower" parameters for the next recursive call.

answered Nov 15, 2010 at 19:41

Brendan

1,87311 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Trevor Arjeski · Accepted Answer · 2010-11-15 19:45:08Z

A guideline to a binary search is to, in this instance, cut the array in half, then check if the comparable object is greater than or equal to the object in the middle of the array. If its smaller you set the upper to one less than the middle (since it has already been checked) and the lower stays the same. If higher, move lower to the middle plus one then the upper stays the same. Keep doing that recursively until you found the object or until it fails when upper == lower.

If you're comparing objects I would write your own compareTo() method in order for you to test if the objects are greater, less or equal to each other.

Collectives™ on Stack Overflow

Java - recursive binary search help

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related