Input: a sequence; output: index in array or pointer to the element in the sequence.
def sequential_search(a:'sequence', x:'num')->int: for i in range(len(a)): if a[i] == x: return i; return -1
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
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.