在递归问题中无法返回基本大小写值

Question

编辑：谢谢你给我的答案！

我刚开始学习数据结构，似乎不明白为什么基本情况不起作用。在这个方法中，我们应该分割我们得到的数组，如果它比分割的地方大/小，就搜索关键字。找到下面的方法(我去掉了大部分sys.out.println，因为堆栈溢出说我有太多代码(：-

public static int nSearch (int n, int a[], int fromIndex, int toIndex, int key){
//base case
if ((toIndex - fromIndex) <= n) 
{ // if there is only one element per split or less
for (int i = fromIndex; i < toIndex; i++) {

if (a[i] == key) {
System.out.println("If a[i] == key runs.");
return i;
}
}
return -1;
}

int splitIndex = a.length/n; //2
if (key >= a[splitIndex]) { // if key is bigger/equal to a[splitIndex], meaning the range is 2-3

nSearch (n, a, splitIndex, a.length, key);

}
else {
//else the range is 0-1
nSearch (n, a, 0, splitIndex, key);
}
return 0;
}

当我发送测试用例时，控制台会返回以下内容：

My Search Tester 2 is Running Now.
Array Length: - 4
Starting nSearch: - n : 2 fromIndex : 0 toIndex : 4
false
Case 1: n = 2 SplitIndex Value = 2 aLength = 4 Key value = 4
Starting nSearch: - n : 2 fromIndex : 2 toIndex : 4
true
Base Case Running
For loop Running
fromIndex : 2 toIndex : 4
i : 2 a[i] : 3 Key : 4
For loop Running
fromIndex : 2 toIndex : 4
i : 3 a[i] : 4 Key : 4
If a[i] == key runs.
Target 4 is at Index := 0

正如您所看到的，输出显示控件进入if (a[i] == key)块，但我不明白为什么return i不起作用。请告诉我我做错了什么。

我不能发布测试人员代码，以免SO拒绝我的帖子，因为它主要是代码，但这是我正在使用的测试用例：

int arr = {1,2,3,4}
nSearch(2, arr, 0, arr.length, 4);

如果有帮助的话，nSearch方法应该是二进制搜索的变体。

Answer 1

我不明白为什么return i不工作

没有理由认为return语句不能像宣传的那样工作，但在大多数情况下，程序会忽略结果返回值。

但请注意方法末尾的return 0。你认为在什么情况下执行是合适的？答案：没有。我怀疑你添加它是为了消除编译器对控制到达非void方法末尾的反对，但如果是这样，那么你应该更深入地研究：为什么控制一开始就达到了那个点？

考虑紧挨在前的位：

if (key >= a[splitIndex]) { // if key is bigger/equal to a[splitIndex], meaning the range is 2-3

nSearch (n, a, splitIndex, a.length, key);

}
else {
//else the range is 0-1
nSearch (n, a, 0, splitIndex, key);
}

在每个分支中，您递归调用nSearch()，但当递归调用返回时会发生什么？没什么特别的。控制只是从那里继续，直接到错误的return 0，它产生测试人员报告的0返回值。递归调用返回的任何值都将被忽略。

你的方法最后几行的这种变体应该更适合你：

if (key >= a[splitIndex]) {          
return nSearch(n, a, splitIndex, a.length, key);
} else {
return nSearch(n, a, 0, splitIndex, key);
}
// return 0;

Answer 2

您应该在从内部递归获得结果后终止递归。此外，在这个nSearch (n, a, splitIndex, a.length, key);中，无论这个方法调用中实际的toIndex是什么，都要检查到a.length(对于fromIndex也是如此(。所以下面的变化应该会给你正确的答案。

if (key >= a[splitIndex]) {          
return nSearch(n, a, splitIndex, toIndex, key);
} 
else {
return nSearch(n, a, fromIndex, splitIndex, key);
}