The element was found!

Sequential Search

The sequential search, also known as linear search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.


function sequentialSearch(toFind, length){
    for(let i = 0; i < length; i++){
        if(i == toFind){
            console.log("Element found!")
            break;
        }
    }
}

The time complexity of Linear Search in the best case is O(1). In the worst case, the time complexity is O(n).

Binary Search

Binary search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.


function binarySearch(toFind, length){
    let l = 0, r = length-1;
    while(l<=r){
        let m = Math.round((l+r)/2);
        if(m == toFind){
            console.log("Element found!")
            break;
        }else if(toFind < m){
            r = m - 1;
        }else{
            l = m + 1;
        }
    }
}

The time complexity of Binary Search in the best case is O(1). In the worst case, the time complexity is O(log n).

Breadth-first search (BFS)

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level . Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.


function bfs(start, m){
    let directions = [[-1,0],[0,1],[1,0],[0,-1]];
    let matrix = [...m];
    let frontier = [];
    frontier.push(start);
    while(frontier.length > 0){
        let node = frontier.shift();
        let x = node[0], y = node[1];
        if (matrix[x][y] === 2){
            break;
        }
        for(let i=0;i < 4; i++){
            let xn = x + directions[i][0];
            let yn = y + directions[i][1];
            if(xn < matrix.length && yn < matrix[0].length && xn >= 0 && yn >= 0){
                let next = matrix[xn][yn];
                if(next === 0){
                    matrix[xn][yn] = -2;
                    frontier.push([xn,yn]);
                }else if(next === 2){
                    frontier.push([xn,yn]);
                }
            }
        }
    }
}

The time complexity can be expressed as O(|V|+|E|), since every vertex and every edge will be explored in the worst case. |V| is the number of vertices and |E| is the number of edges in the graph. Note that O(|E|) may vary between O(1) and O(|V|^{2}), depending on how sparse the input graph is. The space complexity can be expressed as O(|V|).

Depth-first search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.


function dfs(start,m){
    let matrix = [...m];
    let frontier = [];
    frontier.push(start);
    while(frontier.length > 0){
        let node = frontier.pop();
        let x = node[0], y = node[1];
        if (matrix[x][y] === 2){
            break;
        }else if (matrix[x][y] !== 1){
            matrix[x][y] = -2;
        }
        for(let i=0;i < 4; i++){
            let xn = x + directions[i][0];
            let yn = y + directions[i][1];
            if(xn < matrix.length && yn < matrix[0].length && xn >= 0 && yn >= 0){
                let next = matrix[xn][yn];
                if(next === 0 && !includesCoord(xn,yn,frontier)){
                    frontier.unshift([xn,yn]);
                    break;
                }else if(next === 2){
                    frontier.push([xn,yn]);
                }
            }
        }
    }
}

DFS is typically used to traverse an entire graph, and takes time O(|V| + |E|), where |V| is the number of vertices and |E| the number of edges. It also uses space O(|V|) in the worst case to store the stack of vertices on the current search path as well as the set of already-visited vertices.

A* (A-star)

A* is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency. In practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases. A* was created as part of the Shakey project, which had the aim of building a mobile robot that could plan its own actions.

The time complexity is polynomial when the search space is a tree, there is a single goal state, and the heuristic function h meets the following condition: |h(x) - h^*(x)| = O(log h*(x)) where h* is the optimal heuristic, the exact cost to get from x to the goal. The space complexity of A* is O(b^d) where b is the branching factor and d is the depth of the solution . It is roughly the same as that of all other graph search algorithms, as it keeps all generated nodes in memory.