Implement sorted array that always sort when has new data inserted.

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

  def method_missing(m, *args, &block)
    if m == :insert
      p "Direct call method '#{m}' is not support for SortedArray class"
    else
      super
    end
  end

  protected
  def insert(*args)
    super
  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

# a = SortedArray.new
# 10.times { a << rand(100) }
# # a << 9
# # a << 55
# # a << 1234
# # a.insert(0, 16)
# puts a