java - 给定排序数组，如果数组 A 包含元素 A[i] 且 A[i] = i (递归和分而治之)，则返回索引 i

Question

所以我要做一个递归方法，使用分治算法来搜索排序数组并检查 A[i] == i (如果值与数组的当前索引匹配)。现在我不明白为什么我们要使用分治算法，因为我们不寻找特定的值。

在我的脑海中(我是一个初学者)我只想制作一个线性递归方法。给定长度为 n 的数组 A，我们做...

    if(n<0){
return -1;}

if(A[n] == n){
return n;}

else{
return recursiveMethod(Array A, n-1);
}

所以这就是我的想法，但我不知道为什么我们要使用分而治之的算法。无论如何，如果有人能用外行术语解释，因为我是新人，我将不胜感激，谢谢

Answer 1

您的函数需要对大小为 n 的数组进行 n 次比较(我想您已经知道这部分了，它是线性函数中的线性度以及 O(n))。

我们能做得更好吗？

要解决这样的问题，请尝试采用惰性算法，始终寻找不需要完成的工作。在这里，我们可以利用数组已排序的事实来推断我们可以跳过的工作:当 A[i] > i 时，所有值 j = i..A[i] 也必须满足 A[j] > j。假设 A 可能包含重复值。如果 A 中的所有值都必须不同，那么您可以排除比我上面所做的更多的内容...