Create intervals in a sorted array

Question

Let's say I have a sorted array of {1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 21, 23, 25, 26}. I'd like to put these elements into intervals the following way:

1..5
7..10
15..16
21..21
23..23
25..26

In reality I have much bigger data, so I would need an algorithm with a good runtime.

What I had in mind is the following: Separate the array into 2 parts, and with 4 loops go through the array. One loop from 0 index, 2 loop from middle of array and 1 loop from the end of it. Every loop would check if the current and the next element's diff is 1, if yes, then go to next element, else create an interval from previous elements and start a new interval from the next element.

My question is that is it a good approach, or is there a better way? Please pseudo or java code.

Answer 1

Linear solution:

int intervalStart = a[0];
for (int i = 1; i < a.length; ++i) {
    if (a[i] > a[i-1] + 1) {
        outputInterval(intervalStart, a[i-1]);
        intervalStart = a[i];
    }
}
outputInterval(intervalStart, a[a.length-1]);

Runnable version: https://ideone.com/NZ2Uex