5
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @ptwales Please avoid writing your reviews in comments. Since the author has updated the question based on your comments, I have removed the obsolete comments. \$\endgroup\$ Sep 16, 2014 at 22:24
  • 1
    \$\begingroup\$ Array has a bsearch method. \$\endgroup\$
    – steenslag
    Sep 21, 2014 at 19:36

1 Answer 1

2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.