From: William James <w_a_x_man@...>
Date: 2005-08-02T16:31:05+09:00
Subject: Re: algorithm help

Joel VanderWerf wrote:
> Ara.T.Howard wrote:
> > On Tue, 2 Aug 2005, Luiz Esmiralha wrote:
> >
> >> He?s trying to identify all the sequences inside the original array.
> >
> >
> > based on the assumptions that
> >
> >   * array is sorted
> >   * array is huge
> >   * array probably contains zero or one range
> >   * real upper limit of ranges is 2 but, in theory, could be n
> >
> > which makes it a bit easier...
> >
> > cheers.
> >
> > -a
>
> How could the array contain zero ranges? Empty array?
>
> If I understand the practical assumptions we can make, then there are a
> bounded number (1,2) of "gaps" between ranges. Why not just binary
> search for them?

[
[3, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],
[3, 4, 5, 6, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41],
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 37, 38, 39, 40, 41],
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17],
[3, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],
[3, 4, 5, 6, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42],
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 37, 38, 39, 40, 41, 42],
[3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 42]
].each { |dark|

min, max = dark[0], dark[-1]
if((max - min + 1) == dark.size)
  ranges = [ min .. max ]
else
  dif = min
  lower, upper = 0, dark.size-1
  while upper - lower > 1
    print "."
    i = (lower + upper)/2
    if dark[i] - i == dif
      lower = i
    else
      upper = i
    end
  end
  ranges = [ (dark[0]..dark[lower]), (dark[upper]..dark[-1]) ]
end

p ranges
}

-----
ouput:

....[3..3, 28..41]
.....[3..6, 31..41]
.....[3..12, 37..41]
[3..17]
....[3..3, 28..42]
.....[3..6, 31..42]
.....[3..12, 37..42]
.....[3..17, 42..42]