BinarySearch using Recursion in Java

Question

I am learning recursion so trying to practise it by implementing BinarySearch algorithm.

public class BinarySearch {
    public int search(int[] items, int searchTerm, int startIndex, int endIndex) {
        int midIndex = (startIndex + endIndex)/2 ;
        System.out.println("Midpoint: "+midIndex);
        if(searchTerm == items[midIndex]) {
            return midIndex;
        } else if(searchTerm > items[midIndex]) {
            search(items, searchTerm, midIndex, endIndex);
        } else if(searchTerm < items[midIndex]) {
            search(items, searchTerm, startIndex, midIndex);
        } else {
            return -1;
        }
        return -1;
    }

    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int[] items = { 1, 7, 9, 11, 22, 55, 67 };
        int index = bs.search(items, 7, 0, items.length-1);
        System.out.println(index);
    }

}

search is the method that is called recursively with array of items, the value that I want to search and start & end index of the array where item could potentially be there.

First, I get the midpoint and if the item at midpoint matches the searchTerm then I return it. If searchTerm is greater than value at midpoint then I call the search method again with midpoint as startIndex and last item in the array as endIndex.

Similarly, if searchTerm is less than value at midpoint, then pass startIndex and midpoint as start and end value to search in.

Lets say, I want to search for 7. In the first iteration, 3 would be the midpoint so value at index 3 would be 11. Since, 7 < 11, search will be called again with startIndex as 0 and endIndex as 3. Now, midpoint would be 7, so the index of 7 (which is 1) should be returned. However, the value returned is -1 which is not correct.

When I tried troubleshooting it using Eclipse debugger, I found that even after the match is found at

if(searchTerm == items[midIndex]) {
            return midIndex;
}

instead of exiting the method, the below code gets executed

else if(searchTerm < items[midIndex]) {
            search(items, searchTerm, startIndex, midIndex);
        }

And then it returns -1. I feel it could be something to do with recursion as the previous invocation of search() would still be in the stack due to recursive nature of the code and it might be popping out of the stack. However, I can't really understand it. What would be the correct way to implement BinarySearch using recursion?

You're not returning the result of your recursive call: return search(items, searchTerm, startIndex, midIndex); — Joe C
– Joe C, Commented Jul 12, 2017 at 5:13

Holger · Accepted Answer · 2017-07-12 07:08:55Z

2

public int search(int[] items, int searchTerm, int startIndex, int endIndex)
{
  int midIndex = (startIndex + endIndex) / 2; 
  if (startIndex > endIndex)
    return -1;
  else if (searchTerm == items[midIndex]) 
    return midIndex;
  else if (searchTerm < items[midIndex]) 
    return search(items, searchTerm, startIndex, midIndex - 1);
  else // (searchTerm > items[midIndex]) 
    return search(items, searchTerm, midIndex + 1, endIndex);
}

In this version of the binary search I used midIndex ± 1: I did this because in your if statement you already check if items[midIndex] is equal or not to searchTerm, that's why considering items[midIndex] in the next calls is unnecessary.

edited Jul 12, 2017 at 7:08

Holger

301k43 gold badges481 silver badges827 bronze badges

answered Jul 12, 2017 at 5:38

Marco Luzzara

6,1864 gold badges26 silver badges51 bronze badges

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

1 Comment

Holger Over a year ago

midIndex ± 1 is even necessary, as otherwise, this code could end up in an infinite recursion when the value is not in the array. +1

shazin · Accepted Answer · 2017-07-12 05:29:54Z

0

You are not returning your recursive calls.

    public int search(int[] items, int searchTerm, int startIndex, int endIndex) {
        int midIndex = (startIndex + endIndex)/2 ;
        System.out.println("Midpoint: "+midIndex);
        if(searchTerm == items[midIndex]) {
            return midIndex;
        } else if(searchTerm > items[midIndex]) {
            return search(items, searchTerm, midIndex, endIndex);
        } else if(searchTerm < items[midIndex]) {
            return search(items, searchTerm, startIndex, midIndex);
        } else {
            return -1;
        }
        return -1;
    }

UPDATE

Recursion works with a Method Stack as you may know. So when you don't return the value back when you find the element, Your final recursion call will always return -1 as it is the last line in the method.

That is why you got -1.

edited Jul 12, 2017 at 5:29

answered Jul 12, 2017 at 5:14

shazin

22k3 gold badges58 silver badges72 bronze badges

3 Comments

swati Over a year ago

Thank you, that did fix it. Can you please shed some light on what does returning recursive calls imply? Shouldn't the method be added to execution stack regardless?

dantiston Over a year ago

@swati the method is called, but its results are discarded. Then, the return -1 at the end is called. You can see this more clearly in Eclipse if you comment out the final return -1; statement: you should get an error.

Holger Over a year ago

This code doesn’t compile, as now that the missing return statements have been included, the last return -1; is unreachable code. Actually, even the else { return -1; } clause is dead code, as when comparing two int values the result must be one of “equal”, “greater”, or “smaller”, but that won’t be checked by the compiler.

Collectives™ on Stack Overflow

BinarySearch using Recursion in Java

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related