Module: Lite::Containers::SortedArray::BinarySearch

Defined in:
lib/lite/containers/sorted_array/binary_search.rb

Class Method Summary collapse

Class Method Details

.find_position(sorted_array, comparator) ⇒ Object 



14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/lite/containers/sorted_array/binary_search.rb', line 14

def self.find_position(sorted_array, comparator)
  upper = sorted_array.length
  lower = 0
  found = false
  index = lower

  while !found && upper > lower
    index = midpoint(lower, upper)
    candidate = sorted_array[index]
    result = comparator.call(candidate)
    if result.zero?
      found = true
    elsif result.negative?
      upper = index
    else
      index += 1
      lower = index
    end
  end
  [found, index]
end

.midpoint(lower, upper) ⇒ Object 



36
37
38
 
# File 'lib/lite/containers/sorted_array/binary_search.rb', line 36

def self.midpoint(lower, upper)
  ((upper - lower) / 2) + lower
end

.position_of(sorted_array, key, comparison: Helpers::Comparison::Max) ⇒ Object 



9
10
11
12
 
# File 'lib/lite/containers/sorted_array/binary_search.rb', line 9

def self.position_of(sorted_array, key, comparison: Helpers::Comparison::Max)
  comparator = comparison.for_key(key)
  find_position(sorted_array, comparator)
end