SortedArray backed by a binary search for insertion/query

sorted_array.rb

require 'delegate'

# SortedArray is backed by a binary search when inserting elements
# via #<< as well as querying for an element with #include?
#
# Example:
#   a = SortedArray.new
#   10.times { a << rand(100) }
#   puts a # => [3, 24, 30, 40, 42, 43, 49, 67, 81, 88]
#   a.include?(49) # => true
class SortedArray < DelegateClass(Array)
  def initialize
    super([])
  end

  def <<(item)
    insert(search(item).last, item)
  end

  def include?(item)
    search(item).first
  end

  private

  # Returns a [found, index] tuple. found will be true/false
  # depending on whether or not the value was found. index will
  # be the actual position of the element if found, otherwise it
  # will be the proposed insertion position.
  def search(item)
    left, right = 0, size - 1

    while left <= right
      mid = (right + left) / 2
      case item <=> self[mid]
      when 0 then return [true, mid]
      when 1 then left = mid + 1
      when -1 then right = mid - 1
      end
    end

    [false, left]
  end
end