brabuhr
11/6/2008 6:02:00 PM
On Thu, Nov 6, 2008 at 12:39 PM, Pete Hodgson <phodgson@lyris.com> wrote:
> Given a sorted enumeration I need to find the first gap in a sequence.
>
> e.g.
> 3 == find_gap [1,2,4,5]
> nil == find_gap [1,2,3,4]
$ cat bar.rb
def find_gap array
f = array.first
l = array.last
s = l - f + 1
return nil if s == array.size
if array.size == 2
return f + 1
end
c = array.size / 2
if array[c] != f + c
a = find_gap(array[0..c])
else
b = find_gap(array[c..-1])
end
a ? a : b
end
p find_gap([1,2,4,5])
p find_gap([1,2,3,4])
p find_gap([1,2,3,4,5,6,7,11,12])
p find_gap([2,3,4,5,6,7,11,12])
$ ruby bar.rb
3
nil
8
8