首页 文章

如何使用递归进行分而治之以找到A [i] = i

提问于
浏览 次
-1

我正在尝试使用递归二进制搜索方法，以便找到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;
}

这就是我到目前为止所拥有的 .

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

Edit:

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，并且除了最后一个元素之外不存在其他命中） . 除此之外，翻转标志并使用中心作为键完美地工作 . 谢谢！

java recursion binary-search

1 回答

  • 0

    得到它了 . 你有几个基本问题 .

    • 你're confused by the key because you don' t使用它 - 你不需要它 . centre 服务于整个目的 .

    • 对于数组二分，你的逻辑是相反的 . 切换<和> .

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

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

    这将处理除多击案例之外的所有事情 . 要想到这一点，你需要一点最终的逻辑 . 找到解决方案时，请检查原始阵列中心的位置 - 长度（A）/ 2 . 只要使用while循环就可以从 centre 向该方向移动位置i

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

    你不必检查中间元素：要么你已经在那里，要么你知道它不是一个打击 .

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

    回复于

相关问题