Find pairs of numbers in an array that add to 100

find_pairs.rb

# Find pairs that sum to 100
# Input: [13, 2, 14, 3, 13, 97, 13] -> [[3, 97]]
# [1, 99, 1, 99] -> [[1, 99], [1, 99]]
# [50, 50, 50, 50, 50] -> [[50, 50], [50, 50]]

def find_pairs(p_array)
  array = p_array.dup
  sum = 100
  res = []
  while first_num = array.shift
    if i = array.index(100 - first_num)
      second_num = array.slice!(i)
      res.push [first_num, second_num]
    end
  end
  res
end

def find_pairs2(p_array)
  array = p_array.dup
  sum = 100
  res = []
  s_array = array.sort
  while first_num = s_array.shift
    if i = index_binary(s_array, 100 - first_num)
      second_num = s_array.slice!(i)
      res.push [first_num, second_num]
    end
  end
  res
end

def find_pairs3(p_array)
  array = p_array.dup
  sum = 100
  res = []
  holes = []
  count50 = 0
  50.times { holes << [false, false] }
  # the hole is [lownum, highnum] where hole index is distance from 50
  array.each {|i|
    dist = (50-i).abs
    hole = holes[dist]
    if i > 50
      if hole[0]
        holes[dist] = [false, false]
        res.push [50 - dist, 50 + dist]
      else
        hole[1] = true
      end
    elsif i < 50
      if hole[1]
        holes[dist] = [false, false]
        res.push [50 - dist, 50 + dist]
      else
        hole[0] = true
      end
    else
      count50 = count50 + 1
    end
  }
  (count50 / 2).times { res << [50, 50]}
  res
end

def index_binary(arr, looking_for)
  index_binary_im(arr, looking_for, 0, arr.length)
end

def index_binary_im(arr, looking_for, min, max)
  return nil if min == max
  idx = (min + max) / 2
  value_at_idx = arr[idx]
  case looking_for <=> value_at_idx
  when -1
    index_binary_im(arr, looking_for, 0, idx)
  when 1
    index_binary_im(arr, looking_for, idx + 1, max)
  else
    idx
  end
end

awesome_possum = []
(ARGV[0].to_i).times {awesome_possum = awesome_possum + (1..99).to_a}

t = Time.now
find_pairs(awesome_possum).inspect
puts Time.now - t
t = Time.now
find_pairs2(awesome_possum).inspect
puts Time.now - t
t = Time.now
find_pairs3(awesome_possum).inspect
puts Time.now - t
t = Time.now

output

steven-xus-air:tmp steven$ ruby find_pairs.rb 1

0.001047

0.000652

0.000433

steven-xus-air:tmp steven$ ruby find_pairs.rb 10

0.009411

0.007889

0.005189

steven-xus-air:tmp steven$ ruby find_pairs.rb 100

0.232968

0.151368

0.05621

steven-xus-air:tmp steven$ ruby find_pairs.rb 500

5.784909

3.892712

0.226572

steven-xus-air:tmp steven$ ruby find_pairs.rb 100

0.246683

0.152165

0.048657

steven-xus-air:tmp steven$ ruby find_pairs.rb 200

0.749739

0.530505

0.10043

steven-xus-air:tmp steven$ ruby find_pairs.rb 300

1.647357

1.25658

0.145698

steven-xus-air:tmp steven$ ruby find_pairs.rb 400

2.965393

2.321514

0.18469

steven-xus-air:tmp steven$ ruby find_pairs.rb 500

5.723185

4.497201

0.221905

steven-xus-air:tmp steven$ ruby find_pairs.rb 1000

30.94901

22.91157

0.49839