Class: Algorithmable::Searches::BinarySearch

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmable/search/binary_search.rb

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.lookup(element, in_collection) ⇒ Object 



4
5
6
 
# File 'lib/algorithmable/search/binary_search.rb', line 4

def self.lookup(element, in_collection)
  new.lookup(element, in_collection)
end

Instance Method Details

#lookup(element, collection) ⇒ Object 



8
9
10
11
 
# File 'lib/algorithmable/search/binary_search.rb', line 8

def lookup(element, collection)
  return if element.nil?
  traverse element, collection, 0, collection.length - 1
end

#traverse(element, collection, low, high) ⇒ Object 



13
14
15
16
17
18
19
20
21
22
23
24
25
 
# File 'lib/algorithmable/search/binary_search.rb', line 13

def traverse(element, collection, low, high)
  while low <= high
    mid = low + (high - low) / 2
    value_at = collection[mid]
    if element < value_at
      high = mid.pred
    elsif element > value_at
      low = mid.next
    else
      return mid
    end
  end
end