Most used Search Algorithms

A straightforward algorithm that checks each element in a list sequentially until the target element is found or the end of the list is reached.

Time Complexity: O(n) in the worst and average case, O(1) in the best case.

Suitable for small, unsorted lists or when the order of elements is not predictable.

An efficient algorithm for finding a target element within a sorted list. It repeatedly divides the search interval in half. If the middle element matches the target, the search is successful. Otherwise, the search continues in the left or right half depending on whether the target is smaller or larger than the middle element.

Time Complexity: O(log n) in the worst and average case, O(1) in the best case.

Widely used for searching in sorted arrays, databases with indexed columns, and dictionaries.

An improvement over linear search for sorted arrays. It works by jumping ahead by a fixed step size and then performing a linear search within the block where the element might be present.

Time Complexity: O(√n) in the worst case.

Useful for moderately sized sorted arrays where jumping ahead can reduce the number of comparisons compared to linear search.

A graph traversal algorithm that explores as far as possible along each branch before backtracking. Common variations include Pre-order, In-order, and Post-order traversal.

Time Complexity: O(V + E) for graph traversal, O(n) for tree traversal (where V is the number of vertices and E is the number of edges).

Finding paths, detecting cycles in graphs, topological sorting, and exploring tree-like structures.

A graph traversal algorithm that explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Time Complexity: O(V + E) for graph traversal, O(n) for tree traversal.

Finding the shortest path in unweighted graphs, level-order traversal of trees, and network broadcasting.

An informed search algorithm (best-first search) that uses a heuristic function to estimate the cost of reaching the goal from a given node. It combines the actual cost from the start node to the current node and the heuristic estimate to prioritize exploration.

Time Complexity: Depends heavily on the heuristic function. In the worst case, it can be exponential, but with a good heuristic, it can be much more efficient.

Pathfinding in games, robotics, and route planning where an estimate of the remaining cost is available.

A simple algorithm that slides a pattern over the text, one character at a time, and checks for a match at each position.

Time Complexity: O(m*n) in the worst case, where n is the length of the text and m is the length of the pattern.

Suitable for small texts and patterns or as a baseline for comparison.

An efficient string searching algorithm that avoids redundant comparisons by using a precomputed “prefix function” (also known as the “failure function”) to determine how much to shift the pattern when a mismatch occurs.

Time Complexity: O(n + m), where n is the length of the text and m is the length of the pattern.

Widely used in text editors, search engines, and bioinformatics.

Another efficient string searching algorithm that often outperforms KMP in practice. It uses two heuristics (the “bad character” heuristic and the “good suffix” heuristic) to determine larger shifts of the pattern.

Time Complexity: Can be sublinear in many practical cases, with a worst-case of O(n*m), though optimized versions achieve O(n + m).

Commonly used in text editors and search utilities.

A string searching algorithm that uses hashing to find potential matches. It calculates a hash value for the pattern and for substrings of the text and compares these hash values. A match of hash values doesn’t guarantee a true match, so a verification step is needed.

Average Time Complexity: O(n + m), Worst Case: O(m*n) due to hash collisions.

Used in plagiarism detection and finding multiple patterns in a text.

A data structure commonly used in search engines to efficiently retrieve documents containing specific terms. It maps words to the documents they appear in.

Search Complexity: Highly efficient for keyword-based searches.

Foundation of modern search engines like Google and Elasticsearch.

Algorithms like Levenshtein Distance (Edit Distance) and algorithms based on techniques like n-grams are used to find strings that are similar to a query, even if there are typos or variations.

Depends on the specific algorithm and the length of the strings.

Spell checkers, search suggestions, and DNA sequencing.

More advanced techniques that aim to understand the meaning and context of a search query rather than just matching keywords. This often involves using techniques from Natural Language Processing (NLP) and machine learning, such as word embeddings and transformer models.

Varies greatly depending on the complexity of the NLP/ML models used.

Modern search engines, question answering systems, and intelligent assistants.

With the rise of machine learning and embeddings, vector search involves representing data points (text, images, audio) as vectors in a high-dimensional space and finding the nearest neighbors based on distance metrics (e.g., cosine similarity). Libraries like FAISS and Annoy are popular for efficient vector search.

Depends on the indexing and search techniques used (e.g., brute-force, approximate nearest neighbors).

Recommendation systems, image and video retrieval, semantic search, and anomaly detection.