Searching Algorithms

Why Search Matters

Searching is one of the most common operations in programming. Whether you're looking up a user in a database, finding a file on disk, or navigating a map—searching is everywhere.

📋 Linear Search

The simplest search: check each element one by one until you find the target. Works on any data — sorted or unsorted.

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;  // Found at index i
        }
    }
    return -1;  // Not found
}

// Time: O(n) | Space: O(1)

🔍 Binary Search

Divide and conquer: For sorted arrays, compare the target with the middle element and eliminate half the search space each time.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;  // Found!
        } else if (arr[mid] < target) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1; // Search left half
        }
    }

    return -1;  // Not found
}

// Time: O(log n) | Space: O(1)
// IMPORTANT: Array must be sorted!

🌊 Breadth-First Search (BFS)

Explore nodes level by level. Visit all neighbors before moving deeper. Uses a queue (FIFO).

function bfs(graph, start) {
    const visited = new Set();
    const queue = [start];
    const result = [];

    while (queue.length > 0) {
        const node = queue.shift();  // Dequeue

        if (!visited.has(node)) {
            visited.add(node);
            result.push(node);

            // Add all unvisited neighbors to queue
            for (const neighbor of graph[node]) {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                }
            }
        }
    }

    return result;
}

// Example graph: { A: ['B', 'C'], B: ['D'], C: ['E'], D: [], E: [] }
// BFS from A: ['A', 'B', 'C', 'D', 'E']

🏊 Depth-First Search (DFS)

Explore as deep as possible before backtracking. Uses a stack (LIFO) or recursion.

// Recursive DFS
function dfs(graph, node, visited = new Set()) {
    if (visited.has(node)) return;

    visited.add(node);
    console.log(node);  // Process node

    for (const neighbor of graph[node]) {
        dfs(graph, neighbor, visited);
    }
}

// Iterative DFS (using stack)
function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];

    while (stack.length > 0) {
        const node = stack.pop();  // LIFO

        if (!visited.has(node)) {
            visited.add(node);
            console.log(node);

            // Add neighbors to stack
            for (const neighbor of graph[node]) {
                stack.push(neighbor);
            }
        }
    }
}

BFS vs DFS

Quick Reference