遞歸搜索新項目在排序列表中的位置？

我試圖實現一個搜索方法，它返回一個對象的索引，它應該被遞歸地插入到一個排序列表中。遞歸搜索新項目在排序列表中的位置？

這是我的嘗試。

//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

遞歸搜索新項目在排序列表中的位置？

回答

相關問題