递归搜索新项目在排序列表中的位置？

我试图实现一个搜索方法，它返回一个对象的索引，它应该被递归地插入到一个排序列表中。递归搜索新项目在排序列表中的位置？

这是我的尝试。

//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++); 
}

由于某种原因，我似乎得到了StackOverflowError。

来源

2012-02-08 Raju Kumar

你应该使用'++ index'吗？ – Nishant 2012-02-08 08:36:03

即使您修正了由templatetypedef正确标识的错误，您仍然会遇到问题，即您在列表中每个元素都使用了一个堆栈框架，所以只要您的列表大于某个列表，您仍然会遇到问题几千个元素。看看列表是如何分类的，你可能会想要实现一个二分法搜索。 – Dolda2000 2012-02-08 09:22:50

当你说

return search(value,index++);

的index++的效果是“增量指标，再交还该index曾经有过的价值。”这意味着传递给递归调用的index的值将与原始调用中的值相同。我认为，要改变这种阅读

return search(value, index + 1);

哪个更正确地传递的index + 1价值为search。

这里可能有其他错误，但这肯定会导致问题。尝试改变这一点，看看会发生什么。

希望这会有所帮助！

来源

2012-02-08 08:36:25 templatetypedef

'++ index'应该这样做。 – Nishant 2012-02-08 08:39:00

大声笑不能相信我犯了那个错误！ – 2012-02-08 08:39:15

@ Nishant-这是真的，但由于'index'是一个即将超出范围的局部变量，所以我没有看到在这里使用'++ index'的任何理由。副作用是误导性的，对代码进行微小的调整（回到'index ++'）将会破坏它。 – templatetypedef 2012-02-08 08:39:41

难道你没有忘记这种情况吗，你必须在索引之前插入？如果值<排序列表[索引]你的方法调用自身递归不休......

编辑：

如果您修复“指数++”的错误，你现在应该看到，价值观，都应该在不正确的行为在列表的开头插入，而不是附加。

来源

2012-02-08 08:39:17 quaylar

递归搜索新项目在排序列表中的位置？

回答

相关问题