Search Algorithms

Input: a sequence; output: index in array or pointer to the element in the sequence.

Complexity: O(n)

def sequential_search(a:'sequence', x:'num')->int:
for i in range(len(a)):
if a[i] == x:
return i;
return -1

Complexity: O(log(n))

Use: Any sorted indexed collection. Element access must be O(1). Usually used if collection is static, because if it requires insertions/deletions, than element access whould probably not be O(1). In short, good for sorted arrays.

Descrition: Recursively split array into halves and go to he half where the element belongs to. At each iteration 50% of array is discarded from the search. Stop when found or split led to 1 element.

def binary_search(ar:'indexed sequence', x:'num')->int:
start = 0
end = len(ar)-1
i = end // 2
while end > start:
v = ar[i]
if v == x:
return i
elif x < v:
# select the left half
end = i
else:
# select the right half
start = i + 1
i = (end - start) // 2
return -1

Binary search tree

Definition: BST – balanced binary tree with property: left child < parent and parent ≤ right child

Complexity: O(log(n))

Used when there’s a need to maintain sorted order, and there’s a need for fast insertions/deletions. E.g. linked list organized as BST will allow for O(log(n)) searches and O(log(n)) modifications.