class Array
Public Instance Methods
bsearch_first(range = 0...self.length) { |self| ... }
click to toggle source
This method searches the FIRST occurrence which satisfies a condition given by a block in binary fashion and return the index of the first occurrence. Return nil if not found.
# File lib/bsearch20.rb, line 66 def bsearch_first(range = 0...self.length, &block) boundary = bsearch_lower_boundary(range, &block) if boundary >= self.length || yield(self[boundary]) != 0 return nil else return boundary end end
Also aliased as: bsearch
bsearch_last(range = 0...self.length) { |self| ... }
click to toggle source
This method searches the LAST occurrence which satisfies a condition given by a block in binary fashion and return the index of the last occurrence. Return nil if not found.
# File lib/bsearch20.rb, line 99 def bsearch_last(range = 0...self.length, &block) # `- 1' for canceling `lower + 1' in bsearch_upper_boundary. boundary = bsearch_upper_boundary(range, &block) - 1 if (boundary <= -1 || yield(self[boundary]) != 0) return nil else return boundary end end
bsearch_lower_boundary(range = 0...self.length) { |self| ... }
click to toggle source
Return the lower boundary. (inside)
# File lib/bsearch20.rb, line 47 def bsearch_lower_boundary(range = 0...self.length, &block) lower = range.first() -1 upper = if range.exclude_end? then range.last else range.last + 1 end while lower + 1 != upper mid = ((lower + upper) / 2).to_i # for working with mathn.rb (Rational) if yield(self[mid]) < 0 lower = mid else upper = mid end end return upper end
bsearch_range(range = 0...self.length, &block)
click to toggle source
Return the search result as a Range object.
# File lib/bsearch20.rb, line 113 def bsearch_range(range = 0...self.length, &block) lower = bsearch_lower_boundary(range, &block) upper = bsearch_upper_boundary(range, &block) return lower...upper end
bsearch_upper_boundary(range = 0...self.length) { |self| ... }
click to toggle source
Return the upper boundary. (outside)
# File lib/bsearch20.rb, line 80 def bsearch_upper_boundary(range = 0...self.length, &block) lower = range.first() -1 upper = if range.exclude_end? then range.last else range.last + 1 end while lower + 1 != upper mid = ((lower + upper) / 2).to_i # for working with mathn.rb (Rational) if yield(self[mid]) <= 0 lower = mid else upper = mid end end return lower + 1 # outside of the matching range. end