BinarySearchサンプル
class RecordBoundarySearch | |
KeyValue = Struct.new(:key, :value) | |
def initialize(table) | |
@table = table | |
end | |
def first | |
record_boundary(@table.order(id: 'ASC').limit(2)) | |
end | |
def last | |
record_boundary(@table.order(id: 'DESC').limit(2)) | |
end | |
def find(id) | |
record_boundary(@table.where("#{id} <= id").limit(2)) | |
end | |
private | |
def record_boundary(records) | |
if records.size < 2 | |
nil | |
else | |
xs = records.sort_by(&:created_at) | |
RecordBoundary.new( | |
key_value(xs[0]), | |
key_value(xs[1]) | |
) | |
end | |
end | |
def key_value(record) | |
KeyValue.new(record.id, record.created_at) | |
end | |
end | |
class RecordBoundary | |
def initialize(first, second) | |
@first = first | |
@second = second | |
end | |
def key | |
@second.key | |
end | |
def compare(value) | |
if value < @first.value | |
1 | |
elsif @second.value < value | |
-1 | |
else | |
0 | |
end | |
end | |
end | |
class BinarySearch | |
def initialize(searcher) | |
@searcher = searcher | |
end | |
def search(first, last, target) | |
raise BinarySearchTooSmallError.new if 0 < first.compare(target) | |
raise BinarySearchTooLargeError.new if last.compare(target) < 0 | |
search_core(first, last, target) | |
end | |
def search_core(first, last, target) | |
half = (first.key + last.key) / 2 | |
half_result = @searcher.find(half) | |
compare = half_result.compare(target) | |
if 0 < compare | |
search_core(first, half_result, target) | |
elsif compare < 0 | |
search_core(half_result, last, target) | |
else | |
half_result.key | |
end | |
end | |
class BinarySearchBoundaryError < StandardError | |
end | |
class BinarySearchTooSmallError < BinarySearchBoundaryError | |
end | |
class BinarySearchTooLargeError < BinarySearchBoundaryError | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment