Module: BinarySearchFrequency

Included in:
Array
Defined in:
lib/binary_search_frequency/version.rb,
lib/binary_search_frequency/binary_search_frequency.rb

Constant Summary collapse

VERSION = 
"0.0.3"

Instance Method Summary collapse

Instance Method Details

#bfrequency(number) ⇒ Object 



13
14
15
 
# File 'lib/binary_search_frequency/binary_search_frequency.rb', line 13

def bfrequency number
  binary_frequency number
end

#binary_frequency(number) ⇒ Object 



2
3
4
5
6
7
8
9
10
11
 
# File 'lib/binary_search_frequency/binary_search_frequency.rb', line 2

def binary_frequency number
  left_index = left_binary_search(number, 0, size - 1)

  if left_index
    right_index = right_binary_search(number, left_index, size - 1)
    right_index - left_index + 1
  else
    0
  end
end

#left_binary_search(number, left, right) ⇒ Object 



17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/binary_search_frequency/binary_search_frequency.rb', line 17

def left_binary_search number, left, right
  if left <= right
    midpoint_index = (right + left) / 2
    midpoint_value = self[midpoint_index]

    return midpoint_index if midpoint_index.zero? && self[midpoint_index] == number
    if midpoint_value < number
      return midpoint_index + 1 if self[midpoint_index+1] == number
      left_binary_search number, midpoint_index + 1, right
    elsif midpoint_value >= number
      left_binary_search number, left, midpoint_index - 1
    end
  end
end

#right_binary_search(number, left, right) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/binary_search_frequency/binary_search_frequency.rb', line 32

def right_binary_search number, left, right
  if left <= right
    midpoint_index = (right + left) / 2
    midpoint_value = self[midpoint_index]

    return midpoint_index if midpoint_index == size - 1 && self[midpoint_index] == number
    if midpoint_value <= number
      right_binary_search number, midpoint_index + 1, right
    elsif midpoint_value > number
      return midpoint_index - 1 if self[midpoint_index-1] == number
      right_binary_search number, left, midpoint_index - 1
    end
  end
end