二分查找两个有序集合第一次出现不同数据的大小java代码实现

以下是Java代码实现二分查找两个有序集合第一次出现不同数据的大小：

public static int binarySearchFirstDifferentValue(int[] A, int[] B) {
    int left = 0, right = A.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (A[mid] == B[mid]) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    if (left == A.length) {
        return B[right];
    } else {
        return A[left] < B[left] ? A[left] : B[left];
    }
}

其中A和B分别是两个有序集合，函数返回第一个不相同的元素值。

相关问题

二分查找两个大小不同的有序的List集合，找到两个集合第一次出现不同数据的大小，java代码实现

以下是 Java 实现代码：

public class BinarySearch {

    public static void main(String[] args) {
        int[] list1 = {1, 3, 5, 7, 9, 11};
        int[] list2 = {1, 3, 5, 7, 8, 11};
        int index = findFirstDiff(list1, list2);
        if (index == -1) {
            System.out.println("两个集合相同");
        } else {
            System.out.println("第一次出现不同数据的大小为：" + list1[index]);
        }
    }

    public static int findFirstDiff(int[] list1, int[] list2) {
        int low = 0;
        int high = Math.min(list1.length, list2.length) - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (list1[mid] == list2[mid]) {
                low = mid + 1;
            } else if (list1[mid] > list2[mid]) {
                if (mid == 0 || list1[mid - 1] == list2[mid - 1]) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                if (mid == 0 || list1[mid - 1] == list2[mid - 1]) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }
}

该方法利用二分查找的思想，通过比较两个集合的中间元素的大小，来确定两个集合的差异点。在比较的时候，如果中间元素相同，则说明左半部分是相同的，只需要查找右半部分即可；如果中间元素不同，则说明左半部分存在差异，需要继续查找左半部分，直到找到第一个不同的元素。

二分查找两个有序的List集合,并且list集合中的数据从大到小排列，找到两个集合第一次出现不同数据的大小，java代码实现

以下是Java代码实现二分查找两个有序的List集合中第一次出现不同数据的大小：

public static <T extends Comparable<? super T>> T binarySearchFirstDifferentValue(List<T> A, List<T> B) {
    int left = 0, right = A.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        int cmp = A.get(mid).compareTo(B.get(mid));
        if (cmp == 0) {
            left = mid + 1;
        } else if (cmp < 0) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (left == A.size()) {
        return B.get(right);
    } else {
        return A.get(left).compareTo(B.get(left)) < 0 ? A.get(left) : B.get(left);
    }
}

其中A和B分别是两个有序的List集合，函数返回第一个不相同的元素值。由于List集合中的元素类型必须实现Comparable接口，因此我们可以使用T extends Comparable<? super T>来表示泛型类型T必须实现Comparable接口。在比较两个元素大小时，我们使用compareTo方法，它会返回一个整数，表示两个元素的大小关系。如果返回值为0，则说明两个元素相等；如果返回值小于0，则说明A[mid]小于B[mid]；如果返回值大于0，则说明A[mid]大于B[mid]。