Class: Array

Inherits:
Object
  • Object
show all
Defined in:
lib/quartz_torrent/regionmap.rb

Instance Method Summary collapse

Instance Method Details

#binsearch(low = nil, high = nil) ⇒ Object

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.



4
5
6
7
8
9
 
# 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) ⇒ Object

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.



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# 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