Ruby Binary Search

gistfile1.rb

require 'benchmark'

class Data
  class << self
    @@key_values = {}

    def put(key, value, time)
      @@key_values[key] ||= []
      @@key_values[key] << {time: time, value: value}
      true
    end

    # 2 in [1, 2, 3, 4, 5]
    # 3 in [1, 2, 3, 4, 5]
    def get(key, test_time)
      return nil if test_time < @@key_values[key][0][:time]
      iterate_on_positions(@@key_values[key], test_time, 0, @@key_values[key].length - 1)
    end

    def iterate_on_positions(array, test_time, start_pos, end_pos)
      position = ((start_pos + end_pos) / 2).ceil

      puts "Testing at #{position}"

      if start_pos - end_pos == 1
        array[position][:value]
      elsif test_time == array[position][:time]
        array[position][:value]
      elsif test_time < array[position][:time]
        iterate_on_positions(array, test_time, start_pos, position - 1)
      else
        iterate_on_positions(array, test_time, position + 1, end_pos)
      end
    end
  end
end

scale = 100000000

0.upto(scale) do |key|
  Data.put("hello", "hello #{key / (scale / 10.0)}", key / (scale / 10.0))
end

puts Benchmark.measure {
  puts "Value at 7.352352 is #{Data.get("hello", 7.352352)}"
}