Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Algorithms

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.

PreviousSortingNextDynamic Programming

Last updated 1 year ago