Kroeger Simon (ext) <simon.kroeger.ext / siemens.com> wrote:
> 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...

This looks cute.  What makes you sure it's O(log n)?

Btw, here's another funny idea:

-----------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
ranges = []

data.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do |m|
  s = $`.length
  ranges << (s .. (s + m.length - 1))
end

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

Kind regards

    robert