C# 使用递归查找数组中数字的索引

Question

所以在我参加的编程类(class)中，我们学习了递归。我得到了一个任务来编写递归函数，该函数获取排序的数组和一个数字，并返回数组中该数字的索引(如果存在)。

我还不太了解递归的主题，因此我的代码需要一些帮助。我认为我的方向是正确的，但同样，我在这个主题上有点挣扎，所以我想我可以在这里找到指导和帮助。

这是我目前的代码:

private static int arrayIndexValue(int[] arr, int ind)
{
    if (ind > arr.Length/2)
    {
        return arrayIndexValue(arr.Length/2, ind)
    }
    else if (ind < arr.Length/2)
    {
        return arrayIndexValue(arr.Length/2)
    }
}

基本上我想在这里写的是这样的:

如果用户插入的数字小于数组的中间，则继续执行该函数，但将数组减半(二分查找)

如果数字更大，则相同(我建议将我的函数与二进制搜索之类的东西一起使用，但如你所见，我不太清楚如何将它应用到我的代码中)

Answer 1

递归的工作原理是将整个问题分解成更小的部分。如果你在最小的部分(意味着你的数组只有一个值)那么你就会有你的解决方案。这也是您必须处理的第一个案例。

if (arr.Length == 1) return arr[0];

现在你可以开始分解问题了。二进制左或右决定。正如您已经写过的那样，您想要检查天气，该数字是在数组中间的左侧还是右侧。因此，在您的情况下，您需要使用 [ ] 运算符访问数组中的元素:

if (ind > arr[arr.Length / 2]) // check if larger than the middle element

要提取数组的一部分，您需要第二个数组，您可以在其中复制所需的内容。由于您打算只将当前数组的一半传递给递归调用，因此您也只需要一半的大小。

int [] temp = new int[arr.Length / 2];

现在您可以根据条件复制所需的部分(第一个或第二个)，并通过递归调用继续搜索。

要复制数组，您可以使用 Arra.Copy方法。您可以将开始和长度传递给此方法，它会将左侧或右侧的部分复制到 int [] temp 数组中。以下是如何复制正确部分的示例:

Array.Copy(arr, arr.Length / 2, temp, 0, arr.Length / 2);

最后，您需要启动递归调用。此调用将期望新数组和仍然要查找的相同数字。因此，由于您复制了前一个数组的左半部分或右半部分，现在您将新的短数组传递给递归调用:

return arrayIndexValue(temp, ind);

就是这样