这是在排序数组中查找重复项的正确实现吗？

Question

我一直在做一项作业，涉及优化排序数组的重复查找算法，我想了解您对实现的想法。这是我想出的代码：

private static int findDuplicatesFinalVersion(int[] arr1, int[] arr2) {
    int count = 0;
    int index1 = 0;
    int index2 = 0;

    while (index1 < arr1.length && index2 < arr2.length) {
        if (arr1[index1] < arr2[index2]) {
            index1++;
        } else if (arr1[index1] == arr2[index2]) {
            count++;
            index1++;
            index2++;
        } else {
            index2++;
        }
    }
    return count;
}

作业：

跟踪第一个数组中的下一个元素。如果第二个数组中的下一个元素小于第一个数组中的下一个元素，则在第二个数组中向前移动。如果它等于（然后我们发现了重复项）或更大，那么我们在第一个数组中向前移动。假设两个数组本身不包含任何重复项（使用前面示例中的生成器）。运行一些基准测试，并使用以下方法将执行时间与运行时间进行比较：未排序的数组、二分搜索和最终版本。

此实现旨在根据分配要求在两个排序数组中有效地查找重复项。它跟踪两个索引，每个索引对应一个数组，并根据元素的比较智能地推进它们。

在找到这个解决方案之前，我还尝试了未排序的数组并实现了二分搜索，这显着提高了性能。然而，对于这个作业，我的任务是处理排序数组。

如果您有排序和搜索算法的经验，或者遇到过类似的作业，如果您能查看此代码，我将不胜感激。您认为这个实现对于根据我的作业上下文在排序数组中查找重复项是否正确且有效？此外，如果您有任何进一步改进的建议或见解，请随时分享。

谢谢！

Answer 1

我认为你想要找到的是两个排序数组之间的共同元素。为此，您的两个指针方法是正确的。还有另一种可能的解决方案，即遍历两个数组中较小的一个，并针对较小数组中的每个元素，在较大数组上对该元素进行二分搜索。有关此方法的详细说明，请参阅本文中的二分查找（最后一种方法） - Count Common Elements（注意：您可能需要像本文中那样稍微调整逻辑，输入数组按升序和降序排列，但是基本思想保持不变）

现在，就效率而言，双指针方法的工作时间为 O(m + n)，而二分搜索方法的工作时间为 O(nlogm)，其中 m 是较大的数组大小，n 是较小的数组大小。

为了了解其中哪一个更快，我强烈建议您阅读这篇文章 - O(n log m) 与 O(n+m) - 哪个更好？

希望这有帮助！