From: "Kroeger Simon (ext)" <simon.kroeger.ext@...>
Date: 2005-08-05T17:59:13+09:00
Subject: Re: algorithm help

Hi robert, 

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

in fact I think its O(m * log n) with n equals the size of data and m
the
number of ranges.

The algorithm cuts the remaining data in halfs ((p1 + p2) / 2) instead
of 
a linear search. But it has to do it for each range again. 
 
> 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

Rofl, indead a funny idea. For sure the slowest one mentioned here but I

had a realy nice time figuring it out :) (and its short)

But if that's the only concern I would like to make another proposal:

d = [1, 3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
puts d.inject([d[0]..d[0]]){|r,x|r<<(((r.last.end+1>=x)?r.pop.end:
x)..x)}

lets see if you can beat this :))

Simon