BinarySearchサンプル

binary_search.rb

  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