> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/algorithms/searching.md). # 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 ```csharp 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)` ```csharp // 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 queue = new Queue(); // 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. ```csharp public class Graph { public int V { get; set; } // Number of vertices public List> adjList { get; set; } // Adjacency list representation // Constructor to create a graph with V vertices public Graph(int v) { V = v; adjList = new List>(v); for (int i = 0; i < v; i++) { adjList.Add(new List()); } } // 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 queue = new Queue(); // 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. ```csharp 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. ```csharp public class Graph { public int V { get; set; } // Number of vertices public List> adjList { get; set; } // Adjacency list // DFS traversal function public void DFS(int start) { bool[] visited = new bool[V]; // Track visited vertices Stack stack = new Stack(); // 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. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs-57.gitbook.io/data-structure-and-algorithms/algorithms/searching.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.