Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
You can’t perform that action at this time.