Find Holes in Arrays (BSearch).rb

require 'benchmark'

arr = Array(1..9999999)
arr = arr.sample(9999990).sort

def find_minus(p_arr)
  Array(p_arr.first..p_arr.last) - p_arr
end

def find_binary (p_arr)
  return nil if p_arr.empty?
  return Array((p_arr.first+1)..(p_arr.last-1)) if p_arr.size == 2

  v_count = p_arr.last-p_arr.size
  v_center = (p_arr.size / 2)
  v_value = p_arr[v_center]-v_center-p_arr.first

  return find_binary p_arr[0..v_center] if v_count == v_value
  return find_binary p_arr[v_center..(p_arr.size-1)] if 0 == v_value
  return find_binary(p_arr[0..v_center]) + find_binary(p_arr[v_center..(p_arr.size-1)])
end

Benchmark.bm(7) do |x|
  x.report("minus:")   { puts "Skipped by minus #{find_minus arr}" }
  x.report("binary:")  { puts "Skipped by binary #{find_binary arr}" }
end