Two Sum

two-sum.rb

#!/usr/bin/env ruby

def find_pair!(data, target)
  # We know we won't use a value greater than our target
  data.reject! { |i| i > target }
  
  # Sort it so we don't have to scan our list a bunch
  data.sort!
  
  # If our two biggest numbers are lower than the target, we're boned
  raise("not possible") if data[-2] + data[-1] < target
  
  data.each.with_index do |value, index|
    match_index = data.bsearch_index { |datum| value + datum == target }
    return [index,match_index] if match_index
    # TODO: we only have to search 50% of our list since we're matching pairs
  end
  [nil,nil] #failure
end