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:
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.
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.
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).
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.
Last updated