Searching¶
Binary Search¶
Recursively partitions the list until the key is found.
Time Complexity: O(lg n)
Psuedo Code: http://en.wikipedia.org/wiki/Binary_search

algorithms.searching.binary_search.
search
(seq, key)[source]¶ Takes a list of integers and searches if the key is contained within the list.
Parameters:  seq – A list of integers
 key – The integer to be searched for
Return type: The index of where the key is located in the list. If key is not found then False is returned.
BMH Search¶
Search that attempts to find a substring in a string. Uses a badcharacter shift of the rightmost character of the window to compute shifts.
Time: Complexity: O(m + n), where m is the substring to be found.
Space: Complexity: O(m), where m is the substring to be found.
Psuedo Code: https://github.com/FooBarWidget/boyermoorehorspool

algorithms.searching.bmh_search.
search
(text, pattern)[source]¶ Takes a string and searches if the pattern is substring within text.
Parameters:  text – A string that will be searched.
 pattern – A string that will be searched as a substring within text.
Return type: The indices of all occurences of where the substring pattern was found in text.
Depth First Search¶
Recursive implementation of the depth first search algorithm used to traverse trees or graphs. Starts at a selected node (root) and explores the branch as far as possible before backtracking.
Time Complexity: O(E + V)
E = Number of edges
V = Number of vertices (nodes)
Pseudocode: https://en.wikipedia.org/wiki/Depthfirst_search

algorithms.searching.depth_first_search.
dfs
(graph, start, path=[])[source]¶ Depth first search that recursively searches the path. Backtracking occurs only when the last node in the path is visited.
Parameters:  graph – A dictionary of nodes and edges.
 start – The node to start the recursive search with.
 path – A list of edges to search.
Return type: A boolean indicating whether the node is included in the path.
KMP Search¶
Implementation of kmp search on string. Uses a prefix function to reduce the searching time.
Time Complexity: O(n + k), where k is the substring to be found
Psuedo Code: CLRS. Introduction to Algorithms. 3rd ed.

algorithms.searching.kmp_search.
compute_prefix
(word)[source]¶ Returns the prefix of the word.
Parameters: word – The sub string that the prefix will be computed for. Return type: Returns computed prefix of the word.

algorithms.searching.kmp_search.
search
(string, word)[source]¶ Searches for occurrences of a “word” within a main “string” by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing reexamination of previously matched characters.
Parameters:  string – The string to be searched.
 word – The sub string to be searched for.
Return type: The indices of all occurences of where the substring is found in the string.
Implementation of RabinKarp search on a given string.
RabinKarp Search¶
Search for a substring in a given string, by comparing hash values of the strings.
Time Complexity: O(nm)
Psuedo Code: http://en.wikipedia.org/wiki/RabinKarp_algorithm

algorithms.searching.rabinkarp_search.
search
(s, sub)[source]¶ Uses hashing to find any one of a set of pattern strings in a text.
Parameters:  s – The string to be searched.
 sub – The substring to be searched for.
Return type: The indices of all occurences of where the substring is found in the string.