使用二进制搜索查找两个排序数组的所有公共元素

Question

我开始学习Java，所以我有一些愚蠢的问题。我想找到两个排序数组的所有公共元素，使用二进制搜索，下面是我的代码。它运行没有正确的结果。

import java.util.Arrays;

public class CommonElements{
    public static void commonElements(int[] iArr1, int[] iArr2) {
        Arrays.sort(iArr1);
        Arrays.sort(iArr2);
        int index2 = 0, index1 = 0;
        int left1 = 0, right1 = (iArr1.length)-1;

        while (index2 < iArr2.length && index1 < iArr1.length) {
            while (left1 <= right1) {
                int mid1 = (left1 + right1)/2;
                if (iArr2[index2] == iArr1[mid1]) {
                    System.out.print(iArr1[mid1] + " ");
                    index2++;
                } else if (iArr2[index2] > iArr1[mid1])
                    left1 = mid1 + 1;
                else right1 = mid1 - 1;
            }
        }
    }

    public static void main(String[] args) {
        int[] iArr1 = {6,-3,9,-1,0,0,8};
        int[] iArr2 = {-7,6,-3,-5};
        commonElements(iArr1,iArr2);
        System.out.println("END");
    }
}

Answer 1

既然可以只使用两个指针来查找两个排序数组中的公共元素，为什么还要对数组进行二进制搜索？您可以在每次迭代中增加指向两个指针中较小值的指针，如果两个值相等则意味着该元素在两个数组中都是公共的，现在增加两个指针并打印公共元素。

    public static void commonElements(int[] iArr1, int[] iArr2) {
        Arrays.sort(iArr1);
        Arrays.sort(iArr2);
        int index2 = 0, index1 = 0;

        while (index2 < iArr2.length && index1 < iArr1.length) {
            if (iArr2[index2] < iArr1[index1]) {
                index2++;
            } else if (iArr2[index2] > iArr1[index1]) {
                index1++;
            } else {
                System.out.print(iArr1[index1] + " ");
                index1++;
                index2++;
            }
        }
    }

输入：

iArr1 => [-3,-1,0,0,6,8,9], iArr2 => [-7,-5,-3,6]

输出： -3 6

编辑：

如果需要二进制搜索，那么您可以将您的代码编辑成这样，使其不会运行进入无限循环（我已经使用注释标记了更改）：

    public static void commonElements(int[] iArr1, int[] iArr2) {
        Arrays.sort(iArr1);
        Arrays.sort(iArr2);
        int index2 = 0, index1 = 0;

        while (index2 < iArr2.length && index1 < iArr1.length) {
            int left1 = 0, right1 = (iArr1.length)-1; // 1) Reinitialize left1 and right1 in each iteration of iArr2.

            while (left1 <= right1) {
                int mid1 = (left1 + right1)/2;
                if (iArr2[index2] == iArr1[mid1]) {
                    System.out.print(iArr1[mid1] + " ");
                    break; // 2) Break out of the binary search when you've found the common element.
                } else if (iArr2[index2] > iArr1[mid1])
                    left1 = mid1 + 1;
                else right1 = mid1 - 1;
            }

            index2++; // 3) Move to next item of iArr2.
        }
    }

使用二进制搜索查找两个排序数组的所有公共元素

Find all common elements of two sorted arrays use binary search

java

arrays

binary

编辑：