#
# Example:
#
#   % irb -r bsearch.rb
#   irb(main):001:0> [1,2,3,3,3,4,5].bsearch_first {|x| x <=> 3}
#   2
#   irb(main):002:0> [1,2,3,3,3,4,5].bsearch {|x| x <=> 3} # same as above
#   2
#   irb(main):003:0> [1,2,3,3,3,4,5].bsearch_last  {|x| x <=> 3}
#   4
#   irb(main):004:0> [1,2,3,3,3,4,5].bsearch {|x| x <=> 6}
#   nil


class Array
  #
  # This method searches the FIRST occurrence which satisfies a
  # condition of a given block in binary fashion.
  # 
  # This algorithm is extracted from Jon Bentley's
  # Programming Pearls 2nd ed. p.93
  #
  def bsearch_first
    low = -1
    high = self.length
    while low + 1 != high
      mid = (low + high) / 2
      if yield(self[mid]) < 0
	low = mid
      else 
	high = mid
      end
    end

    if high >= self.length || yield(self[high]) != 0
      return nil
    else 
      return high
    end
  end

  alias bsearch bsearch_first

  #
  # This method searches the LAST occurrence which satisfies a
  # condition of a given block in binary fashion.
  # 
  def bsearch_last
    low = -1
    high = self.length
    while low + 1 != high
      mid = (low + high) / 2
      if yield(self[mid]) <= 0
	low = mid
      else 
	high = mid
      end
    end

    if low <= -1 || yield(self[low]) != 0
      return nil
    else
      return low
    end
  end

  #
  # brute force sequential search.
  #
  def search
    self.each_with_index {|x, i|
      return i if yield(x) == 0
    }
    nil
  end
end