Recursively search for where new item goes inside sorted list?

Question

I'm trying to implement a search method, which returns a index of a object where it should be inserted in a sorted list, recursively.

Here is my attempt.

 //listSize is the number of elements inside the sorted list 
 //sortedList is the actual structure holding the values
 // Note: the parameter Value is comparable.  
 public int search(T value,int index){

    if(listSize == 0){
        return 0;
    }
    if(index > listSize){
        return listSize+1; //add at the end
    }
    if(value.compareTo(sortedList[index]) > 0 && value.compareTo(sortedList[index+1]) < 0){
        //value is less 
        return index+1;
    }else if(value.compareTo(sortedList[index]) == 0){
        //both are same
        return index+1;
    }
    return search(value,index++);
}

For some reason I seem to be getting a StackOverflowError.

Answer 1

When you're saying

return search(value,index++);

The effect of index++ is "increment index, then hand back the value that index used to have." This means that the value of index passed into the recursive call will be the same as in the original call. I think you want to change this to read

return search(value, index + 1);

Which more correctly passes the value of index + 1 into search.

There may be other errors here, but this certainly is going to cause problems. Try changing this and see what happens.

Hope this helps!

Answer 2

Didn't you forget the case, that you have to insert before index? If value < sortedList[index] your method will call itself recursively endlessly...

EDIT:

If you fix your "index++" bug, you should now see the incorrect behavior that values that are supposed to be inserted at the beginning of the list, would instead be appended.