bsearch.rb

# Taking on the Binary Search challenge
# http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/

class Array
  # Binary search; assumes array is sorted
  # If value is found in the array, it returns an index where it can be found.
  # If the value occurs multiple times in the array, it will just return the
  # first place it is found (not necessarily the first occurrence in the array).
  # If the value is not found, it returns nil.
  def bsearch(value)
    return nil if self.length == 0
    range = (0..self.length - 1)
    while range.last >= range.first
      mid = (range.last - range.first) / 2 + range.first
      case self.at(mid) <=> value
      when 0 # values are equal
        return mid
      when 1 # mid is greater
        range = (range.first..mid-1)
      when -1 # value is greater
        range = (mid+1..range.last)
      end
    end
    return nil
  end
end