05 Searching (2)

Searching

Linear Search

• Time: O(n)
• Space: O(1)

def linsearch(arr, item):
    for idx in range(len(arr)):
        if arr[idx] == item:
            return idx

Binary Search

• Time: O(log n)
• Space: O(1)

def binsearch(arr, item):
    low = 0
    high = len(arr)-1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == item:
            return mid
        elif arr[mid] < item:
            high = mid-1
        elif arr[mid] > item:
            low = mid + 1
    return -1

Binary Search Trees

Creation

• Time: O(log n)
• Space: O(1)

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
class Tree:
    def __init__(self):
        self.root = None

Counting

• Time: O(n)
• Space: O(1)

def count(tree):
    if tree == None:
        return 0
    else:
        return count(tree.left) + count(tree.right) + 1

Searching

• Time: O(log n)
• Space: O(1)

def search(tree, value):
    if tree == None:
        return False
    elif value < tree.data:
        return search(tree.left)
    elif value > tree.data:
        return search(tree.right)
    elif value == tree.data:
        return True

Insertion

• Time: O(log n)
• Space: O(1)

def insert(tree, value):
    node = Node(value)

    if tree.root == None:
        tree.root = node
    elif value < tree.data:
        if tree.left is None:
            tree.left = node
        else:
            insert(tree.left, value)
    elif value >= tree.data:
        if tree.right is None:
            tree.right = node
        else:
            insert(tree.right, value)

Traversal

Preorder

• Visit root node
• Traverse left subtree
• Traverse right subtree
• Time: O(n)
• Space: O(1)

def preorder(tree):
    if tree == None:
        return
    print(tree.data)
    preorder(tree.left)
    preorder(tree.right)

Inorder

• Traverse left subtree
• Visit root node
• Traverse right subtree
• Time: O(n)
• Space: O(1)

def inorder(tree):
    if tree == None:
        return
    inorder(tree.left)
    print(tree.data)
    inorder(tree.right)

Postorder

• Traverse left subtree
• Traverse right subtree
• Visit root node
• Time: O(n)
• Space: O(1)

def postorder(tree):
    if tree == None:
        return
    postorder(tree.left)
    postorder(tree.right)
    print(tree.data)

Hash Table (Linear Probing)

• Time: O(1), worst O(n)
• Space: O(log n)

def add(table, key):
    start = key % len(table)
    pos = start

    while table[pos] != -1:
        if table[pos] is None:
            table[pos] = key
        pos = (pos + 1) % len(table)
        if pos == start:
            break
    return -1
def search(table, key):
    start = key % len(table)
    pos = start

    while table[pos] != -1:
        if table[pos] == key:
            return pos

        pos = (pos + 1) % len(table)

        if pos == start:
            break

    return -1