Module Algorithms::Search

  1. lib/algorithms/search.rb

This module implements search algorithms. Documentation is provided for each algorithm.

Methods

public class

  1. binary_search
  2. kmp_search

public instance

  1. kmp_search

Public class methods

binary_search (container, item)

Binary Search: This search finds an item in log(n) time provided that the container is already sorted. The method returns the item if it is found, or nil if it is not. If there are duplicates, the first one found is returned, and this is not guaranteed to be the smallest or largest item.

Complexity: O(lg N)

Algorithms::Search.binary_search([1, 2, 3], 1) #=> 1
Algorithms::Search.binary_search([1, 2, 3], 4) #=> nil
[show source]
    # File lib/algorithms/search.rb, line 14
14:   def self.binary_search(container, item)
15:     return nil if item.nil?
16:     low = 0
17:     high = container.size - 1
18:     while low <= high
19:       mid = (low + high) / 2
20:       val = container[mid]
21:       if val > item
22:         high = mid - 1
23:       elsif val < item
24:         low = mid + 1
25:       else
26:         return val
27:       end
28:     end
29:     nil
30:   end
kmp_search (string, substring)

Knuth-Morris-Pratt Algorithm substring search algorithm: Efficiently finds the starting position of a substring in a string. The algorithm calculates the best position to resume searching from if a failure occurs.

The method returns the index of the starting position in the string where the substring is found. If there is no match, nil is returned.

Complexity: O(n + k), where n is the length of the string and k is the length of the substring.

Algorithms::Search.kmp_search("ABC ABCDAB ABCDABCDABDE", "ABCDABD") #=> 15
Algorithms::Search.kmp_search("ABC ABCDAB ABCDABCDABDE", "ABCDEF") #=> nil
[show source]
    # File lib/algorithms/search.rb, line 43
43:   def self.kmp_search(string, substring)
44:     return nil if string.nil? or substring.nil?
45:     
46:     # create failure function table
47:     pos = 2
48:     cnd = 0
49:     failure_table = [-1, 0]
50:     while pos < substring.length
51:       if substring[pos - 1] == substring[cnd]
52:         failure_table[pos] = cnd + 1
53:         pos += 1
54:         cnd += 1
55:       elsif cnd > 0
56:         cnd = failure_table[cnd]
57:       else
58:         failure_table[pos] = 0
59:         pos += 1
60:       end
61:     end
62: 
63:     m = i = 0
64:     while m + i < string.length
65:       if substring[i] == string[m + i]
66:         i += 1
67:         return m if i == substring.length
68:       else
69:         m = m + i - failure_table[i]
70:         i = failure_table[i] if i > 0
71:       end
72:     end
73:     return nil
74:   end

Public instance methods

kmp_search (substring)

Allows kmp_search to be called as an instance method in classes that include the Search module.

class String; include Algorithms::Search; end
"ABC ABCDAB ABCDABCDABDE".kmp_search("ABCDABD") #=> 15
[show source]
    # File lib/algorithms/search.rb, line 80
80:   def kmp_search(substring)
81:     Algorithms::Search.kmp_search(self, substring)
82:   end