Class: VER::BinarySearch

Inherits:
Object
  • Object
show all
Defined in:
lib/ver/vendor/binary_search.rb

Overview

Simple mechanism to do binary search over positive integer space. This allows you to find the last number that is valid for some condition passed in a block in a fast manner rather than doing simple brute-force.

The reason this exists was to find the highest value for the time-to-live arugment to MemCache#store.

Instance Method Summary collapse

Constructor Details

#initialize(works, fails, &block) ⇒ BinarySearch

Returns a new instance of BinarySearch.



33
34
35
36
 
# File 'lib/ver/vendor/binary_search.rb', line 33

def initialize(works, fails, &block)
  @works, @fails = works, fails
  run(&block) if block_given?
end

Instance Method Details

#run ⇒ Object 



38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File 'lib/ver/vendor/binary_search.rb', line 38

def run
  works, fails = @works, @fails
  current = works
  step = 0

  loop do
    success = yield(current)

    if success
      works = current
      current = works + ((fails - works) / 2)
    else
      fails = current
      current = works + ((fails - works) / 2)
    end

    break if current == fails or current == works
    step += 1
  end

  return current
end