From: "Kroeger Simon (ext)" <simon.kroeger.ext@...>
Date: 2005-08-02T19:17:35+09:00
Subject: Re: algorithm help

 
I guess no one cares, but there is an even shorter version
(and it should still be O(log n)):

-------------------------------------------------------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
p1, p2, ranges = 0, (data.size - 1) * 2, [data[0]..data[0]]

until p1 == data.size
    if (d2 = data[p2 = (p1 + p2) / 2]) - (d1 = data[p1]) == p2 - p1
        ranges << ((ranges.last.end+1 >= d1 ? ranges.pop.first :
d1)..d2) 
        p1, p2 = p2+1, data.size - 1
    end
end

puts ranges
-------------------------------------------------------------

I get some odd satisfaction from shrinking stuff, call me stupid...


Simon