Searching

Searching in data structures is the process of locating a specific element (or target value) within a collection of data. It's a fundamental operation crucial for various tasks like retrieval, analysis, and manipulation of data.

Here are common types of searching algorithms:

1. Linear Search:

   • Simplest approach: Checks each element sequentially until the target is found or the end is reached.

   • Time complexity: O(n) in the worst and average cases, O(1) in the best case (if the target is at the beginning).

   • Unsuitable for large datasets due to its linear time complexity.

2. Binary Search:

   • Efficient algorithm for sorted arrays: Repeatedly divides the search interval in half until the target is found or the interval is empty. Requires a sorted array.

   • Time complexity: O(log n) in the worst, average, and best cases.

   • Significantly faster than linear search for large datasets.

3. Binary Search Tree:

   • Creates a binary search tree (BST) from the input data.

   • Performs an in-order traversal of the BST to retrieve elements in sorted order.

   • Time complexity: O(n log n) average case, O(n^2) worst case (skewed trees).

4. Graph Traversal:

   • Uses algorithms like depth-first search (DFS), breadth-first search (BFS) or Kahn's algorithm. The BFS used to find closest elements where else DFS to check if element or path exists.

   • Algorithms like Dijkstra's and Bellman-Ford involve sorting edges or vertices based on their distances or weights.

Factors to consider when choosing a search algorithm:

• Data structure: The type of data structure used to store the elements (e.g., array, list, tree).

• Order of elements: Whether the elements are sorted or unsorted.

• Size of the dataset: The number of elements to be searched.

• Frequency of searches: How often searches are performed.

• Time complexity: How long the algorithm takes to run in terms of input size.

• Space complexity: How much extra memory the algorithm requires.

Examples

    public static int BinarySearch(int[] arr, int target)
    {
        int low = 0;
        int high = arr.Length - 1;

        while (low <= high)
        {
            int mid = low + (high - low) / 2; // Prevent potential overflow

            if (arr[mid] == target)
            {
                return mid; // Target found
            }
            else if (arr[mid] < target)
            {
                low = mid + 1; // Search in the right half
            }
            else
            {
                high = mid - 1; // Search in the left half
            }
        }

        return -1; // Target not found
    }

Complexity

• Time complexity: O(log N)

• Space complexity: O(1)

// Node structure for the linked list tree
public class Node
{
    public int data;
    public Node left, right;

    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}

// BFS traversal function
public void BFS(Node root)
{
    if (root == null)
    {
        return; // Handle empty tree
    }

    Queue<Node> queue = new Queue<Node>(); // Use a queue for level-order traversal
    queue.Enqueue(root); // Enqueue the root node

    while (queue.Count > 0)
    {
        // Dequeue a node from the queue and print its data
        Node current = queue.Dequeue();
        Console.Write(current.data + " ");

        // Enqueue the left and right children of the current node, if they exist
        if (current.left != null)
        {
            queue.Enqueue(current.left);
        }
        if (current.right != null)
        {
            queue.Enqueue(current.right);
        }
    }
}

Complexity

• Time complexity: O(V) , where V is the number of nodes.

• Space complexity: O(V) , where V is the number of nodes.

public class Graph
{
    public int V { get; set; } // Number of vertices
    public List<List<int>> adjList { get; set; } // Adjacency list representation

    // Constructor to create a graph with V vertices
    public Graph(int v)
    {
        V = v;
        adjList = new List<List<int>>(v);
        for (int i = 0; i < v; i++)
        {
            adjList.Add(new List<int>());
        }
    }

    // Function to add an edge to the graph
    public void AddEdge(int u, int v)
    {
        adjList[u].Add(v); // Add v to u's list of neighbors
    }

    // BFS traversal from a given starting vertex
    public void BFS(int start)
    {
        bool[] visited = new bool[V]; // Track visited vertices
        Queue<int> queue = new Queue<int>(); // Queue for level-order traversal

        visited[start] = true; // Mark the starting vertex as visited
        queue.Enqueue(start); // Enqueue the starting vertex

        Console.Write("BFS traversal: ");

        while (queue.Count > 0)
        {
            // Dequeue a vertex from the queue and print it
            int u = queue.Dequeue();
            Console.Write(u + " ");

            // Explore all unvisited neighbors of u
            foreach (int v in adjList[u])
            {
                if (!visited[v])
                {
                    visited[v] = true; // Mark the neighbor as visited
                    queue.Enqueue(v); // Enqueue the neighbor for further exploration
                }
            }
        }
    }
}

Complexity

• Time complexity: O(V+E),where V is the number of vertices and E is the number of edges.

• Space complexity: O(V) for the visited array and queue.

public void PreOrderTraversal(Node root)
{
    if (root == null)
    {
        return;
    }

    Console.Write(root.data + " "); // Visit the root first
    PreOrderTraversal(root.left);  // Recursively traverse the left subtree
    PreOrderTraversal(root.right); // Recursively traverse the right subtree
}

public void InOrderTraversal(Node root)
{
    if (root == null)
    {
        return;
    }

    InOrderTraversal(root.left);  // Recursively traverse the left subtree
    Console.Write(root.data + " "); // Visit the root after the left subtree
    InOrderTraversal(root.right); // Recursively traverse the right subtree
}

public void PostOrderTraversal(Node root)
{
    if (root == null)
    {
        return;
    }

    PostOrderTraversal(root.left);  // Recursively traverse the left subtree
    PostOrderTraversal(root.right); // Recursively traverse the right subtree
    Console.Write(root.data + " "); // Visit the root last
}

Complexity

• Time complexity: O(V) , where V is the number of nodes.

• Space complexity: O(V) , where V is the number of nodes.

public class Graph
{
    public int V { get; set; } // Number of vertices
    public List<List<int>> adjList { get; set; } // Adjacency list

    // DFS traversal function
    public void DFS(int start)
    {
        bool[] visited = new bool[V]; // Track visited vertices
        Stack<int> stack = new Stack<int>(); // Use a stack for depth-first traversal

        stack.Push(start); // Push the starting vertex onto the stack
        visited[start] = true; // Mark it as visited

        Console.Write("DFS traversal: ");

        while (stack.Count > 0)
        {
            int u = stack.Pop(); // Pop a vertex from the stack
            Console.Write(u + " ");

            // Explore unvisited neighbors in reverse order (for a more consistent traversal)
            for (int i = adjList[u].Count - 1; i >= 0; i--)
            {
                int v = adjList[u][i];
                if (!visited[v])
                {
                    stack.Push(v);
                    visited[v] = true;
                }
            }
        }
    }
}

Complexity

• Time complexity: O(V+E),where V is the number of vertices and E is the number of edges.

• Space complexity: O(V) for the visited array and stack.