Binary search a Rails model by created_at when created_at is not indexed

binary_search.rb

# binary search by ID to find record of type `model` whose created_at is closest to `timestamp`.
# assumes created_at is a monotonically increasing function of ID.
# `low_end_bias` is used to begin the search somewhere other than the first
# model ever. it's a percentage of records. useful when you know that the thing
# you're looking for is near the end of the list, which is the case for the
# thing I'm currently looking for, so I'm defaulting it to 0.99

def find_closest_to(model, timestamp, low_end_bias = 0.99)
  high_mark = model.last
  low_id = (high_mark.id * low_end_bias).round
  low_id = 1 if low_id == 0
  low_mark = model.find(low_id)

  # a better implementation would just recurse with a lower initial bias
  throw 'try a lower low_end_bias' if low_mark.created_at > timestamp

  loop do
    midpoint = [low_mark.id, high_mark.id].sum / 2
    candidate = model.find(midpoint)
    candidate_delta = candidate.created_at - timestamp
    if candidate_delta > 0
      high_mark = candidate
    else
      low_mark = candidate
    end

    return low_mark if high_mark.id - low_mark.id < 2
  end
end

# initial condition
# ........L...T...........H
#
# find candidate in midpoint of L&H
# ........L...T....C......H
#
# candidate is higher than target, so it becomes new H
# ........L...T....H.......
#
# find candidate in midpoint of L&H
# ........L...TC...H.......
#
# candidate is higher than target, so it becomes new H
# ........L...TH...........
#
# find candidate in midpoint of L&H
# ........L.C.TH...........
#
# candidate is lower than target, so it becomes new L
# ..........L.TH...........
#
# eventually, when L&H get close enough together, return L