class Array
Public Instance Methods
binsearch(low = nil, high = nil) { |x| ... }
click to toggle source
Perform a binary search for a value in the array between the index low and high. This method expects a block. The block is passed a value v, and should return true if the target value is >= v, and false otherwise.
# File lib/quartz_torrent/regionmap.rb, line 4 def binsearch(low = nil, high = nil) return nil if length == 0 result = binsearch_index(low, high){ |x| yield x if !x.nil?} result = at(result) if result result end
binsearch_index(low = nil, high = nil) { |at(low)| ... }
click to toggle source
Perform a binary search for an index in the array between the index low and high. This method expects a block. The block is passed a value v, and should return true if the target value is >= v, and false otherwise.
# File lib/quartz_torrent/regionmap.rb, line 13 def binsearch_index(low = nil, high = nil) return nil if length == 0 low = 0 if !low high = length if !high if low == high if yield at(low) return low else return nil end end mid = (high-low)/2 + low if yield at(mid) # this value >= target. result = binsearch_index(low, mid == low ? mid : mid-1){ |x| yield x if !x.nil?} if result return result else return mid end else # this value < target binsearch_index(mid == high ? mid : mid+1, high){ |x| yield x if !x.nil?} end end