A small improve on v1.4.8 14.1 binary search solution

#1

The binary search solution in my version can have a little improvement.
The code use binary search to check whether elements in short array is in the longer array. Every time it will search the whole array. But the longer array is also sorted. So previous binary search result (either found, the index of the element, or didn’t find, the index of insertion position) will provide a new starting position for next binary search: the next element in short array must be larger than this element, so its position in longer array must be after the position we just got. So instead of searching n times whole longer array, we only need to search n times partition of the longer array. It should help a little. My java code:

public int[] intersection(final int[] a, final int[] b)
    {
        int[] result = {};
        int num = 0;
        if (null != a && a.length != 0 && b != null && b.length != 0)
        {
            result = new int [Math.min(a.length, b.length)];
            final int[] t1 = (a.length <= b.length) ? a : b;
            final int[] t2 = (t1 == a) ? b : a;
            
            int start = 0;
            for (final int value : t1)
            {
                final int index = Arrays.binarySearch(t2, start, t2.length, value);
                if (index >= 0)
                {
                    result[num++] = value;
                    start = index + 1;
                }
                else
                {
                    start = -(index + 1);
                }
            }
        }
        
        return Arrays.copyOf(result, num);
    }
0 Likes
#2

There seems to be a minor bug in the solution above.
if index = Arrays.BinarySearch() returns the length of the t2 array, you should exit out of the for loop and return result. Otherwise, there is a chance to crash the program if t1 still has more elements

A slightly modified solution would be:

public int[] intersection(final int[] a, final int[] b)
{
int[] result = {};
int num = 0;
if (null != a && a.length != 0 && b != null && b.length != 0)
{
result = new int [Math.min(a.length, b.length)];
final int[] t1 = (a.length <= b.length) ? a : b;
final int[] t2 = (t1 == a) ? b : a;

        int start = 0;
        for (final int value : t1)
        {
            final int index = Arrays.binarySearch(t2, start, t2.length, value);
            if (index >= 0)
            {
                result[num++] = value;
                start = index + 1;
            }
            else
            {
               if (-(index) == t2.Length)
                   break;
                start = -(index + 1);
            }
        }
    }

    return Arrays.copyOf(result, num);
}
0 Likes
#3

I like the idea of shrinking the array you are searching for each round. Although it won’t improve the worst case time complexity, it should play well in practice without doubt. Besides, it well utilizes the result of binary search in Java, which C++ one does not have such feature.

Thanks for the wonderful discussion brought from you two, and please keep that!

0 Likes
#4

I didn’t notice that, thank you very much.

0 Likes