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.