Java Recursion Problem

Question

Hi, I have this bit of code to do some testing before I implement it. Basically on the second recursive call it should enter in on this line ( else if( sec >= 1 ) { return test( s ,lowerBounds + middle + 1, upperBounds ); } ) but it does not instead it goes on to the other else if and changes the value of sec. Am I missing something?

public class Main
{
    private static String[] test = { "aaa", "aab", "aac", "aad", "aae" };

    public static void main( String[] args ) {
        System.out.println( test( "aab", 0, 4 ) );
    }

    public static int test( String s, int lowerBounds, int upperBounds ) {
        if( upperBounds < lowerBounds || upperBounds > lowerBounds ) {

            int middle = ( upperBounds – lowerBounds ) / 2;
            int sec = s.compareTo(test[lowerBounds + middle]);

            if( sec == 0 )
                { return lowerBounds + middle; }
            else if( sec <= -1 )
                { return test( s, lowerBounds, upperBounds – middle – 1 ); }
            else if( sec >= 1 )
                { return test( s ,lowerBounds + middle + 1, upperBounds ); }
        } else { return -1; }
        return -10;
    }
}

EDIT: Sorry I should have said this is my own implementation of binary searching. I am still learning programming on my own so please do not flame me if I have messed it up somehow.

EDIT: If I remove the first if statement it looks as though it works fine?

Answer 1

This line

if( upperBounds < lowerBounds || upperBounds > lowerBounds )

looks suspicious. If your upperBounds is lower than your lowerBounds, then middle will be negative. Normally, this should happen only at the end of your recursion (either when you found the proper element, or when it does not exists). This might be why your recursion works if you remove this if statement (however things will break if you call the function badly).

Also, why are you comparing with test[lowerBounds + middle] ?

int sec = s.compareTo(test[lowerBounds + middle]);

The idea of binary sorting is that you compute the middle position (if it makes sense) of your bounds, and you compare the element at the middle with the element you're looking for.

If the middle is bigger, (and assuming your array is sorted), you must look 'on the left side'. If if is lower, you look 'on the right side'. Your test will only work at the first recursion, since lowerBounds is 0.

Hoping this helps.

Answer 2

HAHAHA

Thank you late night that was an obvious one. How's this?

if( !(upperBounds < lowerBounds) || !(upperBounds > lowerBounds) ) {

Thank you so so much.

Answer 3

if( upperBounds < lowerBounds || upperBounds > lowerBounds )

is true for every number except for the case where upperBounds == lowerBounds.