Find missing numbers in a sorted array
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 &lt;= 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 &lt; 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&lt;Integer&gt;() 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 &lt;&gt; on the right-hand side. The code:


private List&lt;Integer&gt; missing = new ArrayList();



should be:

private List&lt;Integer&gt; missing = new ArrayList&lt;&gt;();


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