Searching

Binary Search

Runtime

$O (lo g n)$

Pseudocode

import math

def binary_search(a, b):
    left = 1
    right = len(a)
    while left <= right:
        middle = math.floor((left + right) / 2)
        if a[middle] == b:
            return middle
        else if a[middle] > b:
            right = middle - 1
        else:
            left = middle + 1
    return "not present"

Further Resources

Binary search algorithm - Wikipedia

Interpolation Search

Runtime

Best-Case: $O (lo g lo g n)$

Worst-Case: $O (n)$

Pseudocode

def interpolation_search(a, b):
    left = 1
    right = len(a)
    while left <= right:
        middle = (b - a[left]) / (a[right] - a[left])
        if a[middle] == b:
            return middle
        else if a[middle] > b:
            right = middle - 1
        else:
            left = middle + 1
    return "not present"

Further Resources

Interpolation search - Wikipedia

Linear Search

Runtime

$O (n)$

Pseudocode

def linear_search(a, b):
    for el in a:
        if el == b:
            return b
    return "not present"

Further Resources

Linear search - Wikipedia

Lower Bound for Comparison-Based Searching

Is it possible to sort in under $Θ (lo g n)$ comparisons?

Every comparison-based searching algorithm corresponds to some binary decision tree. Then the elements of the searched array correspond to the nodes of that tree. Therefore there are $n$ nodes in the tree. The worst-case runtime corresponds to the height of the tree, denoted by $h$ .

A tree that has height $h$ must have no more than $2^{h}$ nodes, thus

$⟺ 2^{h} > 1 + 2 + 2^{2} + \dots + 2^{h - 1} = 2^{h} - 1 \geq n h \geq lo g n \geq Ω (lo g n)$

Breadth-First Search (BFS)

Runtime

$O (∣ V ∣ + ∣ E ∣)$

Pseudocode

def bfs(s, graph):
    q = Queue(s)
    dist = [None] * len(graph.nodes)
    enter = [None] * len(graph.nodes)
    leave = [None] * len(graph.nodes)
    dist[s] = 0
    enter[s] = 0
    t = 1
    while !q.isEmpty():
        u = q.dequeue()
        leave[u] = t
        t = t + 1
        for v in u.children:
            if !enter[v]:
                q.enqueue(v)
                dist[v] = dist[u] + 1
                enter[v] = t
                t = t + 1
    return dist

Further Resources

Breadth-first search - Wikipedia

Depth-First Search (DFS)

Runtime

$O (∣ V ∣ + ∣ E ∣)$

Pseudocode

def dfs(s, graph):
    q = Stack(s)
    dist = [None] * len(graph.nodes)
    enter = [None] * len(graph.nodes)
    leave = [None] * len(graph.nodes)
    dist[s] = 0
    enter[s] = 0
    t = 1
    while !q.isEmpty():
        u = q.pop()
        leave[u] = t
        t = t + 1
        for v in u.children:
            if !enter[v]:
                q.push(v)
                dist[v] = dist[u] + 1
                enter[v] = t
                t = t + 1
    return dist

Further Resources

Depth-first search - Wikipedia