Binary Search in Ruby

Question

I want to write a search that raises an error if the list supplied is not sorted.

class BinarySearch

  attr_accessor :list

  def initialize(orig)
    raise ArgumentError unless sorted? orig
    self.list = orig   
  end

  def search_for(n)   
    s_list = self.list 
    offset = 0
    loop do
      mid = s_list.length/2
      left = s_list[0..mid-1]
      right = s_list[mid+1..s_list.length-1]
      mid_val = s_list[mid]
      if n == mid_val
        return offset+mid 
      elsif n > mid_val
        offset += mid+1
        s_list = right
      else
        s_list = left
      end    
      raise RuntimeError if s_list.empty?
    end
  end

  def middle
   self.list.length/2
  end  

  private

  def sorted?(orig)
    for i in 1..orig.length-1
        return false if orig[i] < orig[i-1]
    end 
    return true   
  end



end

Answer 1

Same concept as yours, but slimmed down a bit, and avoiding an explicit loop.

You might also consider making this a utility function, or a mixin with which you can dynamically extend Enumerable objects. Making it a class which creates a special object wrapper over a list, for the purpose of adding a single method, has a clunky java-esque feel.

Also, keep in the mind the below is optimized for readability and brevity, not for speed. In particular, left_of and right_of are making unnecessary copies of the array halves.

class BinarySearch

  attr_accessor :list

  def initialize(orig)
    raise ArgumentError unless sorted? orig
    @list = orig   
  end

  def search_for(n, s_list = list, offset = 0)   

    raise RuntimeError if s_list.empty?

    mid = s_list.length / 2
    mid_val = s_list[mid]

    return mid + offset if mid_val == n
    return search_for(n, left_of(s_list, mid), offset) if mid_val > n
    search_for(n, right_of(s_list, mid), offset+mid+1)

  end

  private

  def left_of(s_list, i)
    s_list[0..i-1]
  end

  def right_of(s_list, i)
    s_list[i+1..-1]
  end

  def sorted?(orig)
    orig.each_cons(2).all? { |a,b| (a <=> b) <= 0 }
  end

end