algorithms.search

Binary Search

In computer science, binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

binary_search(sorted_array, target_element)

Binary search algorithm

Parameters:

• sorted_array – list of sorted elements (integers)
• target_element – element to find

Returns:

position of target_element if succes -1 if element is not found

Examples

>>> binary_search([1, 2, 3, 4], 5)
-1

>>> binary_search([x for x in range(10000)], 26)
26

Closest Pair

The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean plane[1] was among the first geometric problems that were treated at the origins of the systematic study of the computational complexity of geometric algorithms. [Wikipedia]

brute_force_distance(points)

Brute force solution for closest pair problem

Complexity: O(n^2)

Parameters:points – list of points in the following format [(x1, y1), (x2, y2), … , (xn, yn)] Returns:Minimum distance between points

Examples

>>> n_log_n_squared_distance([(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)])
1.4142135623730951

n_log_n_squared_distance(points)

O(N (LogN)^2) solution for closest pair problem

Complexity: O(n (log n)^2)

Parameters:points – list of points in the following format [(x1, y1), (x2, y2), … , (xn, yn)] Returns:Minimum distance between points

Examples

>>> n_log_n_squared_distance([(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)])
1.4142135623730951

Fibonacci

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

fibonacci(number)

Recursive implementation of fibonacci function

Parameters:number – number in fibonacci sequence Returns:fibonacci number

Examples

>>> fibonacci_recursive(20)
6765

Fibonacci with modulo

Calculating (n-th Fibonacci number) mod m

fibonacci_modulo(number, modulo)

Calculating (n-th Fibonacci number) mod m

Parameters:

• number – fibonacci number
• modulo – modulo

Returns:

(n-th Fibonacci number) mod m

Examples

>>> fibonacci_modulo(11527523930876953, 26673)
10552

Rabin-Karp

In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find any one of a set of pattern strings in a text. For text of length n and p patterns of combined length m,

its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm).

rabin_karp(text, pattern)

Rabin-Karp algorithm that finds all occurrences of pattern in text

Parameters:

• text – text to search in
• pattern – pattern to search for

Returns:

list of position where pattern placed in text

Examples

>>> rabin_karp('AABAACAADAABAABA', 'AABA')
[0, 9, 12]

>>> rabin_karp('aaaaa', 'aaa')
[0, 1, 2]