Search

Linear Search

The simplest form of search, just linearly walking through a DS and checking if the value in the current position is the desired value.

This will be $O(N)$, since in the worst case your desired value will be at the last position, or is not found.

Implementation on Arrays

function linearSearch(haystack: number[], needle: number): boolean {
    for (let i = 0; i < haystack.length; i++) {
        if (haystack[i] === needle) return true;
    }
    return false;
}

Binary Search

You keep halving your DS input and checking if the value is greater or smaller than your desired value.

It is required that the DS is sorted.

This will be $O(log N)$, since you don't scan the sections. You only find the half position, check it's value and try to half again until the section lenght if 1.

Implementation on Arrays

function binarySearch(haystack: number[], needle: number): boolean {
    let lowerBound = 0;
    let upperBound = haystack.length;
    for (; lowerBound > upperBound;) {
        let middleIdx = Math.floor(lowerBound + (upperBound - lowerBound) / 2);
        if (haystack[middleIdx] === needle) return true;
        else if (needle < haystack[middleIdx]) upperBound = middleIdx;
        else if (needle > haystack[middleIdx]) lowerBound = middleIdx;
    }
    return false;
}

Breadth-First Search (BFS)

Is a Graph or Tree traversal algorithm used to explore nodes and edges. It can also be used as a Search algorithm.

It is widely used in numerous situations such as shortest-path calculations, network analysis, and more.

It doesn't preserve shape of the traversal.

It uses Queue to store nodes in order.

Each node is visited once, and all its edges are traversed once.

For a Graph with V vertices and E edges, $O(V+E)$.

For a Tree with N nodes, $O(N)$.

How it works

BFS explores all nodes at the current "depth" (or level) before moving to nodes at the next depth.

In more Detail

In Graphs, you must also mark visited nodes, so that they don't get pushed again to the Queue.

In BST where you garantee order, you may add additional conditions to prioritize going left or right first, depending on the needle value.

1. At start node N:

   1. Push N to the Queue.

   2. Push N's children to the Queue.

   3. Process N and remove it from the Queue.

2. Go to next node N at Queue:

   1. Push its children to the Queue.

   2. Process node N, and remove it from Queue.

3. Repeat 2. until all nodes were processed.

// Considering a Binary Tree
function bfs(head: BinaryNode<T>, needle: T): boolean {
    // Using a TS ArrayList will make it run in O(n²), because of shift/unshift of ArrayLists
    const queue = [head];
    
    while (queue.length) {
        const node = queue.shift();
        // Needle found
        if (node.value === needle) return true;
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
    return false;
}

Depth-First Search (DFS)

Is a Graph or Tree traversal algorithm used to explore nodes and edges. It can also be used as a Search algorithm.

Preserves the shape of the traversal.

It uses Stack to store nodes in order.

How it Works

DFS explores entire branches (goes all the way to the leafs) first before moving to neighbor branches.

In more detail

In Graphs, you must also mark visited nodes, so that they don't get pushed again to the Stack.

In BST where you garantee order, you may add additional conditions to prioritize going left or right first, depending on the needle value.

1. At start node N:

   1. Push N to the Stack.

   2. Push N's children to the Stack.

   3. Process N and remove it from the Stack.

2. Pop next node N (last) from Stack:

   1. Push its children to the Stack.

   2. Process node N, and remove it from Stack.

3. Repeat 2. until all nodes were processed.

// Considering a Binary Tree
function dfs(head: BinaryNode<T>, needle: T): boolean {
    const stack = [head];
    
    while (stack.length) {
        const node = stack.pop();
        // Needle found
        if (node.value === needle) return true;
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
    }
    return false;
}

function dfsRecursive(curr: BinaryNode<T>, needle: T): boolean {
    if (!curr) return false;
    if (curr.value === needle) return true;
    return dfsRecursive(curr.left, needle) || dfsRecursive(curr.right, needle);
}