只有 2 个参数的递归二分搜索方法
好的，这是学校作业。我在进行递归二分搜索时没有遇到任何问题，但分配明确指出该方法应该只接受 2 个参数，即列表和您正在搜索的项目。这就是我有点迷失的地方。
public int binarySearch(List<Card> cards, Card key)
{
int mid = (cards.size()) / 2;
if(cards.size() == 1) {
if(key.equals(cards.get(0))) {
return 0;
}
}
else {
if(key.equals(cards.get(mid))) {
return mid;
}
else if(key.compareTo(cards.get(mid)) == - 1) {
return binarySearch(cards.subList(0, mid), key);
}
else if(key.compareTo(cards.get(mid)) == 1) {
return mid + 1 + binarySearch(cards.subList(mid + 1, cards.size()), key);
}
}
return -1;
}
所以这会很好地工作，除非我正在搜索不存在的东西并且它属于列表的上半部分。因为我只传递 2 个参数，所以我必须在每次递归调用时更改列表，但是，如果它位于上半部分，我就不能丢失索引位置，所以我必须通过递归调用将它们添加到那里，如果它最终不在上半部分，然后返回 -1 + 我之前考虑的所有索引。有没有办法可以清除所有内容并使其返回-1？任何建议表示赞赏。
Okay so this is for a school assignment. I have had no problems doing a recursive binary search but the assignment specifically says that the method should only take 2 arguments, the list, and the item you are searching for. This is where I am getting a little lost.
public int binarySearch(List<Card> cards, Card key)
{
int mid = (cards.size()) / 2;
if(cards.size() == 1) {
if(key.equals(cards.get(0))) {
return 0;
}
}
else {
if(key.equals(cards.get(mid))) {
return mid;
}
else if(key.compareTo(cards.get(mid)) == - 1) {
return binarySearch(cards.subList(0, mid), key);
}
else if(key.compareTo(cards.get(mid)) == 1) {
return mid + 1 + binarySearch(cards.subList(mid + 1, cards.size()), key);
}
}
return -1;
}
So this will work fine unless I am searching for something that doesn't exist and it belongs in the upper half of the list. Because I am only passing through 2 arguments, I have to change the list with each recursive call, however, if it's in the upper half i can't lose my index spot so I have to add those on there with the recursive call, if it ends up not being in the upper half then it returns -1 + all those indexes i was accounting for previously. Is there a way I can clear it all out and make it just return -1? Any advise is appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
缓存并测试函数调用的结果，如果返回-1，否则计算并返回。
Cache and test the result of the function call, if -1 return, else calculate and return.
您可以使用两种方法，其中一种方法调用另一种方法。公共方法公开了您的作业所需的两个参数接口。它还可以检查空参数 - 这种事情只需要在开始时检查一次。
您的第二个方法是私有的，只能从第一个方法内部调用。这是标准的递归二分搜索，具有您需要的多个参数。
You could use two methods, where one calls the other. The public method exposes the two parameter interface your homework needs. It can also check for null parameters - the sort of things that only need checking once, right at the beginning.
Your second method is private and is only called from inside your first method. That is your standard recursive binary search, with as many parameters as you need.
在添加索引之前，您可以检查该块中的递归binarySearch调用的结果是否为-1：
You can check if the result of the recursive binarySearch call in that block is -1 before you add the indexes: