如何在分而治之时使用递归来找到 A[i] = i

Question

我正在尝试使用递归二进制搜索方法来查找 A[i] = i 给定的 'n' 个按升序排序的不同数量的元素。

我知道如何在给定我需要搜索的目标的情况下使用递归二进制搜索方法，但是当我必须将键值递增 1 并在 A[i] = 时搜索时，我似乎无法实现i.

public static int match_dac( int[] A, int n )
{
    return dnq(A, 0, n-1, 0);
} 

public static int dnq(int[] A, int left, int right, int key) {
    if (left < right) {
        int centre= (left + right) / 2;
         if (A[centre] < centre) {
            return dnq(A, left, centre, key+1); 
        } else if (A[centre] > centre) {
            return dnq(A, centre + 1, right, key + 1);
        } else {
            return centre;
        }


    }

    return -1;
}

这是我目前所拥有的。

任何帮助将不胜感激，谢谢！

编辑：

public static int match_dac( int[] A, int n )
{
    return dnq(A, 0, n - 1);

} 

public static int dnq(int[] A, int left, int right) {
    if (left < right) {
        int centre= (left + right) / 2;
        if (A[centre] > centre) {
            return dnq(A, left, centre); 
        } else if (A[centre] < centre) {
            return dnq(A, centre + 1, right);
        } else {
            return centre;
        }
    } else if (left == right) {
        if (left == A[right])
            return left;
    }
    return -1;
}

现在可以使用了，感谢您的帮助。我在最后一个 else if 语句中添加了因为我的方法没有捕获最后一个元素是否等于相应的索引（即当数组大小为 9 时 A[8] = 8，并且除了最后一个元素之外不存在其他命中） .除此之外，翻转标志并使用中心作为键非常有效。谢谢！

Answer 1

知道了。你有几个基本问题。

您对密钥感到困惑，因为您没有使用它 -- 而且您没有需要它。 centre 服务于整个目的。
你的逻辑与数组平分相反。切换 < 和 >。

此外，match_dac 有一个多余的参数：如果我们有 A，我们可以简单地导出 n。摆脱那个参数，然后简单地调用

dnq(a, 0, length(A)-1)

这将处理除多次命中情况外的所有情况。为此，您需要一点最终逻辑。当您找到解决方案时，请检查您距离原始数组中心的位置 -- length(A)/2。使用 while 循环将位置 i 从 centre 朝那个方向移动，只要

A[i] == i and i != length(A)/2

您不必检查中间元素：您已经在那里，或者您知道它不是命中。

你能做出这些改变吗？我没有在这台机器上完全安装 Java 工作环境，或者我可以直接给你工作代码。

如何在分而治之时使用递归来找到 A[i] = i

How to use recursion on divide and conquer to find A[i] = i

java

recursion

binary-search