Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Two Sum
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment