Finding the intersection and union in two sorted Lists

[lewis manuel]

This is an assignment that I've been doing and the specifications for it are that I need to implement two methods(intersection and union) using the comparable interface(only allowed to use Java Collection API basic methods) and explain their complexity.

I've finished the first part(creating the intersection method) and described it's complexity.

The way I did it was by using a binary search on the second sort list while using a for loop for the first list so I can traverse through the first list and second list in one go. If I find a match in both sorted lists, then I add them to a list that contains all objects that are distinct and are the intersection of List 1 and List 2.

In essence, the time complexity for my method is nlogn. the n is for the for loop through the first list. The logn is because of the binary search. I don't know if it possible to make it a little bit better.

public class UnionAndIntersection<T>
{
    public static <T extends Comparable<? super T>> void intersection(List<T> L1, List<T> L2, List<T> result)
    {
        T target;
        T previous = null;
        boolean found;
        

        for(int i = 0; i < L1.size(); i++)
        {
            target = L1.get(i);
            found = binarySearch(L2, target);
            
            if(found == true && previous != target)
            {
                result.add(target);
                previous = target;
            }
        }
    }

    public static <T extends Comparable<? super T>> boolean binarySearch(List<T> items, T target, int first, int last)
    {
        if (first > last)
        {
            return false;
        }
        else
        {
            int middle = (first + last) / 2; // Calculation to find the middle
            int compResult = target.compareTo(items.get(middle)); // use the compareTo method from the comparable interface.
            
            if(compResult == 0)
            {
                return true; // We have found our target;
            }
            else if (compResult < 0) // Move to the left
            {
                return binarySearch(items, target, first, middle - 1);
            }
            else // Move to the right
            {
                return binarySearch(items, target, middle + 1, last);
            }
        }
    }

    /*Helper method*/
    public static <T extends Comparable<? super T>> boolean binarySearch(List<T> items, T target)
    {
        return binarySearch(items, target, 0, items.size() - 1);
    }

    public static void display(List list)
    {
        for(Object object : list)
        {
            System.out.print(object + " ");
        }
    }

    public static void main(String[] args)
    {
         List<Integer> L1 = new ArrayList<>();
         List<Integer> L2 = new ArrayList<>();
         List<Integer> result = new ArrayList<>();
         L1.addAll(Arrays.asList(4, 6, 6, 8, 12));
         L2.addAll(Arrays.asList(4, 6, 6, 6, 10));
         intersection(L1, L2, result);
         System.out.print("The objects in these two lists that intersect are: ");
         display(result); // Prints out 4 and 6 as it should.
    }
}

I notice that my previous code didn't check for duplicates. What I added is a variable previous that keeps track of the previous element that was found. Why I think this works is because we have a sorted list. We can have a sorted list that have duplicates like this {6, 6, 6} but not a list like this {4, 6, 4}. What this means is that the duplicate has to always be behind the element that was found previously given by the rule that we have a sorted list which or may not contain duplicates.

[Piet Souris]

You could make it a little better, although I think it is still nlogn.
Suppose your lists are A and B, and that the first element of A
equals the nth element of B. Then for the second element of A,
you only need to look at B, starting from position n + 1 (or n,
depending how you handle duplicates).

[lewis manuel]

I've changed the intersection to look like this

public static <T extends Comparable<? super T>> void intersection(List<T> L1, List<T> L2, List<T> result)
    {
        T target;
        T previous = null;
        boolean found;
        int index = 0;

        target = L1.get(index);

        do
        {
            if(previous != target)
            {
                found = binarySearch(L2, target);

                if(found == true)
                {
                    result.add(target);
                    previous = target;
                }
            }

            index++;
            target = L1.get(index);
        }
        while (index < L1.size() - 1);
    }

Suppose if we have these sorted lists

A = {1, 2, 6, 9, 9}
B = {1, 2, 9 12}

For these two lists I would have to do four binary searches instead of five. The previous code did 5 anyways even though there is no point because you have a duplicate.