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

• 200_success: @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.
• steenslag: Array has a bsearch method.

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