CODEWITHSUNDEEP
java
swati
swati

Reputation: 1267

BinarySearch using Recursion in Java

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?

Upvotes: 0

Views: 99

Answers (2)

Marco Luzzara
Marco Luzzara

Reputation: 6026

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.

Upvotes: 2

shazin
shazin

Reputation: 21883

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.

Upvotes: 0

Related Questions