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