return in if jumps to return on the end of the method-CodePudding

I want to create a binarySearch algorithm as recursion. The code should be ok, since everything is working as i want it to.

This is my code:

public class Searcher {

    public static <T extends Comparable<T>> int binarySearchRecursive(T[] values, T key) {
        int start = 0;
        int end = values.length - 1;
        int mid = (start   end) / 2;

        return binarySearchRecursive(values, key, start, end, mid);
    }

    public static <T extends Comparable<T>> int binarySearchRecursive(T[] values, T key, int start, int end, int mid) {
        if (key.compareTo(values[mid]) == 0) {
            return mid;
        } else if (key.compareTo(values[mid]) < 0) {
            end = mid;
            mid = (start   end) / 2;
            binarySearchRecursive(values, key, start, end, mid);
        } else if (key.compareTo(values[mid]) > 0) {
            start = mid;
            mid = (start   end) / 2;
            binarySearchRecursive(values, key, start, end, mid);
        }

        return -1;
    }
}

The test for it is the following:

class SearcherTest {
    private Integer[] values;

    @BeforeEach
    void setUp() {
        values = new Integer[]{1, 3, 5, 7, 9, 11};
    }

    @Test
    void binarySearchRecursive() {
        for (int i = 0; i < values.length; i  ) {
            assertEquals(i, Searcher.binarySearchRecursive(values, values[i]),
                    "binary search should return index for included values");
        }

        assertEquals(-1, Searcher.binarySearchRecursive(values, 100),
                "binary search should return -1 for not included values");
    }
}

While debugging, everything works as intended. Although after jumping in the if
if (key.compareTo(values[mid]) == 0) { return mid; is executed, but jumps immediately to the return -1 on the end and doesnt give the wanted mid int back.

How could i solve it and give mid back instead of -1?

Thanks for your help!

CodePudding user response：

it seems you have a rather simple mistake you just forgot to return the value from the recursion.

simply adding a return statment before the call to binarySearchRecursive(values, key, start, end, mid); should fix it.

so your code would look like this:

public class Searcher {

    public static <T extends Comparable<T>> int binarySearchRecursive(T[] values, T key) {
        int start = 0;
        int end = values.length - 1;
        int mid = (start   end) / 2;

        return binarySearchRecursive(values, key, start, end, mid);
    }

    public static <T extends Comparable<T>> int binarySearchRecursive(T[] values, T key, int start, int end, int mid) {
        if (key.compareTo(values[mid]) == 0) {
            return mid;
        } else if (key.compareTo(values[mid]) < 0) {
            end = mid;
            mid = (start   end) / 2;
            return binarySearchRecursive(values, key, start, end, mid);
        } else if (key.compareTo(values[mid]) > 0) {
            start = mid;
            mid = (start   end) / 2;
            return binarySearchRecursive(values, key, start, end, mid);
        }
        return -1;
    }
}

hope this helps! happy coding!

EDIT: To clear up some missunderstanding, in the debugger it doesn't just jump out of the if-statment when hitting the return. it leaves the method and enteres the method where it left of previously. this is best explaned with an example.

if we have a tree like this:

     3
   /   \
  1     5 
 / \   / \
0   2 4   6

and want to find the value 2, we start at the top (mid) we see that 2 != 3 so we go left. we need to expicitly tell the computer to return our anwser even if it is not currently found, because we will only find it once we have done some recursion steps. when we are at the left branch we see that 2 != 1 and go right. again we need to expicitly tell the computer to return the answer it find's in that branch of the tree, since we are not there yet. now when we get to 2 == 2 the anwser is accepted, but returning it we only get back one layer in the recurison. as mentioned before we need to propagate the result we got to the top by keep returning it.

if this is still a bit confusion you may need to learn a bit about how recursion works (mainly the stack which is used)

CodePudding user response：

Soo, thanks to your answers i updated my code and it's working now!

    public static <T extends Comparable<T>> int binarySearchRecursive(T[] values, T key) {
        return binarySearchRecursive(values, 0, values.length - 1, key);
    }

    public static <T extends Comparable<T>> int binarySearchRecursive(T[] values, int start, int end, T key) {
        if (end < start) {
            return -1;
        }

        int mid = start   ((end - start) >> 1);

        if (key.compareTo(values[mid]) == 0) {
            return mid;
        } else if (key.compareTo(values[mid]) < 0) {
            return binarySearchRecursive(values, start, mid - 1, key);
        } else return binarySearchRecursive(values, mid   1, end, key);
    }