Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
This is the complete cheatsheet for all the Searching Algorithms that will act as a summary of each concepts including time complexity, key weakness and strengths.
Search algorithms are used to find and retrieve information from a database. They are an essential component of modern computer science and are widely used in many applications, such as web search engines, online shopping, and recommendation systems.
Search Algorithms for Arrays
| Search Algorithms | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Space Complexity | Idea | When to use |
|---|---|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(n) | It is a simple search algorithm that searches for an item in a list one by one. It is useful when the size of the data set is small. | When you are dealing with a small dataset. When you need to find an exact value. When you are searching a dataset stored in contiguous memory. |
| Binary Search | O(1) | O(log n) | O(log n) | O(1)->iterative, O(logN)->recursive | It is an efficient search algorithm that works on sorted data sets. It uses a divide-and-conquer approach to find the target item in logarithmic time. | Binary search requires the data to be sorted. The size of the data set is large: When you need to find a specific value. Minimizing the number of comparisons. |
| HashSet | O(1) | O(1) | O(1)) | O(n) | Hash set is a data structure that stores unique elements and implements set operations, such as union, intersection, and difference. Elements are stored in a hash table, where the indices are determined by the results of a hash function applied to the elements. | HashSet offers constant-time performance for the basic operations (add, remove, contains). It is used when you want to store unique elements, without any specific order. |
Linear Search
function linearSearch(arr: number[], value: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i;
}
return -1;
}
}
Binary Search
int binarySearch(int[] A, int x)
{
int low = 0, high = A.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (x == A[mid]) {
return mid;
}
else if (x < A[mid]) {
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
Searching Algorithm for Graphs
| Search Algorithms | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Space Complexity | Idea | When to use |
|---|---|---|---|---|---|---|
| Depth-First Search (DFS) | O(1) | O(V + E) | O(V + E) | O(V) | It is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It is used for finding connected components and searching mazes. | When you want to do graph traversal, topological sorting, path finding. |
| Breadth-First Search (BFS) | O(1) | O(V+E) | O(V+E) | O(V) | It is a graph traversal algorithm that explores all the vertices at the same depth before moving on to the next level. It is used for finding the shortest path and the minimum number of steps to reach a goal state. | When you want to find shortest paths, and finding connected components. |
| Greedy Best-First Search | O(n) | O(b^m) | O(b^d) | O(b^d) | It is a search algorithm that uses a heuristic function to estimate the cost of reaching the goal and selects the node with the lowest estimated cost at each step. | It is used when the solution can be evaluated using a heuristic function. The heuristic function provides an estimate of the cost to reach the goal. The goal is to find a path with the lowest estimated cost |
| Dijkstra’s Algorithm | O(ElogV) | O(E + V log V) | O(E + V log V) | O(V) | It is a shortest-path algorithm that finds the shortest path from a source node to all other nodes in a weighted graph. It uses a priority queue to select the node with the lowest cost at each step. | It is used when used when the problem requires finding the shortest path between two nodes in a graph. The edge weights are non-negative. |
| A* Search | O(b^d) | O(b^d) | O(b^m) | O(b^d) | It is an informed search algorithm that combines the best of DFS and BFS. It uses a heuristic function to estimate the cost of reaching the goal and selects the path with the lowest estimated cost. | where finding the shortest path between two nodes is important. |
Probabilistic Search Algorithms
| Search Algorithms | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Space Complexity | Idea | When to use |
|---|---|---|---|---|---|---|
| Bloom filter | O(1) | O(1) | O(1) | O(n) | A Bloom filter is a probabilistic data structure that is used to test whether an element is a member of a set. A hash function is used to map elements to bits in a bit array. To insert an element into the set, multiple hash values are calculated and the corresponding bits in the bit array are set to 1. | sed in situations where it is important to test set membership quickly, but with a small probability of false positives like spell checking, duplicate detection. |
| Cuckoo filter | O(1) | O(1) | O(1) | O((log2(1/ϵ)+2)/α ) | Cuckoo filter stores the fingerprint of the value to be stored in an array of buckets. Cuckoo hashing is a method used to avoid collisions in a hash table. | Used to test set membership and support adding and deleting items efficiently. They are an alternative to Bloom filters and offer some advantages, including better false positive rates, lower memory usage, and the ability to delete elements. |
| Interpolation Search | O(log(logn)) | O(log(logn)) | O(n) | O(1) | Interpolation Search is a search algorithm used for searching for a key in a dataset with uniform distribution of its values. An improved binary search for sorted and equally distributed data. | Used to find the position of a target value within a sorted array or list. In numerical search, cryptography and database indexing. |
