Find missing numbers in a sorted array

Array of size \$(n-m)\$ with numbers from \$1..n\$ with \$m\$ of them missing. Find all of the missing numbers. The array is sorted.


Example: If arr = [1,2,4,5,6,8], result should be 3 & 7.

Here is my code which I would like to get reviewed:

import java.util.*;

class FindMissingNumsArray {

    private List missing = new ArrayList();

    private void findMissingNums(int[] array) {
        if(array == null)
            return;
        int length = array.length - 1;
        if(length  1; diff--) {
                if(!missing.contains(array[i] + c))
                    missing.add(array[i] + c);
                c++;
            }
            i++;
        }
        while(j  1; diff--) {
                if(!missing.contains(array[j] + a))
                    missing.add(array[j] + a);
                a++;
            }
            j++;
        }
    }

    private void printMissingList() {
        for(int i: missing)
            System.out.print(i + " ");
    }

    public static void main(String[] args) {
        int[] array = {1, 4, 5, 6, 9, 10, 12, 15, 19};
        int[] array1 = {0, 5, 6, 9, 10};
        FindMissingNumsArray findMissings = new FindMissingNumsArray();
        findMissings.findMissingNums(array);

        System.out.print("Missing numbers in array are: ");
        findMissings.printMissingList();

        findMissings.missing = new ArrayList();
        findMissings.findMissingNums(array1);

        System.out.print("Missing numbers in array1 are: ");
        findMissings.printMissingList();
    }
}

I know there are ways to implement this better in terms of logic, run time, data structures, etc. It will be nice to know what I can do to improve the code.

Sometimes (actually, normally), simpler is better.

I'm going to present a different way of doing this that's really simple, if you understand the tricks, then I'm going to explain what makes it better. One of the reasons I am doing it this way is because your code is hard to follow.... simply because there's so much. I suspect that when you see a different way of doing things a penny will "drop".

Here's the alternative:

private static final int[] findMissing(int[] data) {
    if (data == null || data.length <= 1) {
        // nothing missing.
        return new int[0];
    }
    int first = data[0];
    int last = data[data.length - 1];
    int[] missing = new int[last - first - data.length + 1];
    int missingCursor = 0;
    int expect = first;
    for (int value : data) {
        while (expect < value) {
            missing[missingCursor] = expect;
            missingCursor++;
            expect++;
        }
        expect++;
    }
    return missing;
}

Is that it? Yes, and it is probably still too much. But, let's consider the problem...

• for too-small inputs, we know that there's nothing missing.

• for larger inputs, we know exactly how much is missing - the difference between the first and last data values, less the number of values we actually have, and, add 1 because the last-minus-first is actually 1 too small.

• then, all we have to do is 'expect' certain values, and fill in the gaps until we get the values we expect.

So, that is what the code does, but, note the following:

• there is no need for object-oriented programming - there is no object here to represent. A single static method works fine.

• there is no need for an adjustable-size ArrayList() because we know how much is missing. Also, that's converting int values to Integer members in a List, which is more work than needed.

• the method assumes the inputs are valid - no error-handling or validation

Now, that's the way I would write that method, and why I think it is an improvement.

Having said that, I want to point out some other issues in the code:

-
When creating a collection like an ArrayList, you need to use the diamond operator <> on the right-hand side. The code:

private List missing = new ArrayList();

should be:

private List missing = new ArrayList<>();

On the other hand, I really like that you have made the left-side List, this shows an understanding of the Collections API

-
When I run your code, the order of the missing values in the first array is suspect. I get: 2 3 7 8 11 16 17 18 13 14 (yes, the 13 and 14 are at the end for some reason). There's a bug in there somewhere I can't find.

-
Your code should print a new line after each output. Currently it is all on one line. System.out.println() to do that.

See this running in Ideone

StackExchange Code Review Q#93278, answer score: 6