From: brabuhr@...
Date: 2008-11-07T03:02:13+09:00
Subject: Re: Finding gaps in a sorted sequence

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