Common Search Algorithms to Know for Intro to Algorithms

Search algorithms are essential tools for finding values in data structures. From simple methods like linear search to more advanced techniques like A* search, each algorithm has its strengths and weaknesses, impacting efficiency and performance in various scenarios.

1. Linear Search

   • Searches for a target value by checking each element in a list sequentially.
   • Time complexity is O(n), making it inefficient for large datasets.
   • Works on both sorted and unsorted lists, providing flexibility in usage.

2. Binary Search

   • Requires a sorted list and divides the search interval in half with each step.
   • Time complexity is O(log n), significantly faster than linear search for large datasets.
   • Efficiently narrows down the potential location of the target value.

3. Depth-First Search (DFS)

   • Explores as far down a branch of a tree or graph before backtracking.
   • Can be implemented using recursion or a stack data structure.
   • Time complexity is O(V + E), where V is vertices and E is edges, making it suitable for traversing large graphs.

4. Breadth-First Search (BFS)

   • Explores all neighbors at the present depth prior to moving on to nodes at the next depth level.
   • Utilizes a queue data structure for implementation.
   • Time complexity is O(V + E), making it effective for finding the shortest path in unweighted graphs.

5. A Search Algorithm*

   • Combines features of both DFS and BFS, using heuristics to guide the search.
   • Time complexity can vary, but it is generally efficient for pathfinding and graph traversal.
   • Guarantees the shortest path if the heuristic is admissible (never overestimates the cost).

6. Jump Search

   • Works on sorted arrays by jumping ahead by fixed steps and then performing a linear search within the block.
   • Time complexity is O(√n), providing a balance between linear and binary search.
   • More efficient than linear search but requires the array to be sorted.

7. Interpolation Search

   • An improvement over binary search for uniformly distributed data, estimating the position of the target.
   • Time complexity can be O(log log n) in the best case, but O(n) in the worst case for non-uniform distributions.
   • Requires a sorted array and is more efficient than binary search when the data is uniformly distributed.

8. Exponential Search

   • Combines binary search with an exponential search strategy to find the range of the target value.
   • Time complexity is O(log n) for the search phase, making it efficient for unbounded or infinite lists.
   • Particularly useful when the size of the dataset is unknown.