Common Search Algorithms

Why This Matters

Search algorithms form the backbone of nearly every program you'll encounter, from finding a contact in your phone to GPS navigation plotting your route. In this course, you're being tested on your ability to analyze time complexity, space complexity, and algorithmic trade-offs. Understanding search algorithms means understanding how computer scientists solve the fundamental problem of locating data efficiently, and why choosing the wrong algorithm can mean the difference between milliseconds and hours of computation.

Don't just memorize that binary search is $O(\log n)$. Know why it achieves that complexity through interval halving, when it applies (sorted data only), and how it compares to alternatives. Exam questions will ask you to select the right algorithm for a scenario, analyze worst-case performance, or trace through an algorithm's execution. Master the underlying mechanisms, and you'll handle any variation they throw at you.

---

Sequential and Array-Based Searches

These algorithms work directly on arrays or lists, moving through elements in predictable patterns. The key distinction is whether they require sorted data and how they reduce the search space.

Linear Search

Linear search is the simplest approach: start at index 0 and check every element one by one until you find the target or reach the end of the list.

• Time complexity: $O(n)$ in both the worst and average case. This makes it the baseline against which faster algorithms are measured.
• No sorting required. That's its main advantage. If you can't guarantee your data is ordered, linear search is your only option among these array-based methods.
• Best-case is $O(1)$ if the target happens to be the first element.

Binary Search

Binary search works by comparing the target to the middle element of a sorted array. If the target is smaller, you discard the right half; if larger, you discard the left half. Each comparison cuts the remaining search space in half.

• Time complexity: $O(\log n)$, because halving $n$ elements repeatedly takes about $\log_2 n$ steps to reach a single element.
• Requires sorted data. If the data arrives unsorted, you'll need to sort it first at a cost of $O(n \log n)$. That's still worth it if you're performing many searches on the same dataset.
• Can be implemented iteratively or recursively. Both have the same time complexity, but the iterative version uses $O(1)$ space while the recursive version uses $O(\log n)$ stack space.

Tracing through an example: Say you're searching for 7 in the sorted array [1, 3, 5, 7, 9, 11].

1. Middle element is 5 (index 2). 7 > 5, so search the right half: [7, 9, 11].
2. Middle element is 9 (index 4). 7 < 9, so search the left half: [7].
3. Middle element is 7. Found it in 3 comparisons instead of 4 with linear search.

Jump Search

Jump search splits the difference between linear and binary search. You jump ahead by a fixed block size (optimally $\sqrt{n}$), and once you've jumped past the target, you do a linear search backward within that block.

• Time complexity: $O(\sqrt{n})$, which sits between linear's $O(n)$ and binary's $O(\log n)$.
• Requires sorted data. It's most useful in situations where jumping forward is cheap but random access is expensive, like searching through data stored on physical media or in certain linked structures.

---

Optimized Array Searches

These algorithms improve on binary search for specific data distributions or unknown dataset sizes. They exploit mathematical properties of the data to make smarter guesses about target location.

Interpolation Search

Instead of always checking the middle element, interpolation search estimates where the target is likely to be based on its value. Think about how you'd search a dictionary: if you're looking for "walrus," you'd open near the back, not the middle.

The position estimate uses this formula:

$pos = low + \frac{(target - arr[low]) \times (high - low)}{arr[high] - arr[low]}$

• Best-case complexity: $O(\log \log n)$ when data is uniformly distributed. That's dramatically faster than binary search for large datasets.
• Worst-case complexity: $O(n)$ when the distribution is heavily skewed, because the position estimates become inaccurate.
• Requires sorted, uniformly distributed data to perform well. If you can't guarantee uniform distribution, stick with binary search.

Exponential Search

Exponential search is designed for situations where you don't know the size of the dataset. It works in two phases:

1. Find the range: Start at index 1, then double the index (1, 2, 4, 8, 16, ...) until you find a value greater than the target.
2. Binary search within that range: Once you've found the upper bound, apply binary search on the narrowed interval.

• Time complexity: $O(\log n)$ overall. The range-finding phase takes $O(\log n)$ steps, and the binary search within the identified range also takes $O(\log n)$.
• Ideal for unbounded or infinite lists where standard binary search can't compute a midpoint because you don't know the array's length.

---

Graph Traversal Algorithms

These algorithms navigate nodes and edges rather than array indices. The fundamental choice is between exploring deep (DFS) or wide (BFS), and that choice determines what kind of solution you find first.

Depth-First Search (DFS)

DFS picks one path and follows it as far as possible before backtracking. When it reaches a dead end (a node with no unvisited neighbors), it returns to the most recent node that still has unexplored options.

• Time complexity: $O(V + E)$ where $V$ is the number of vertices and $E$ is the number of edges. You visit every vertex and check every edge once.
• Implementation: Uses a stack, either explicitly or through recursion's call stack.
• Space complexity: $O(V)$ for the stack in the worst case (a graph shaped like a long chain).
• Best for: Cycle detection, topological sorting, solving mazes, and checking if a path exists between two nodes.

Breadth-First Search (BFS)

BFS explores all neighbors of the current node before moving to the next level of depth. This level-by-level approach guarantees that you discover closer nodes before farther ones.

• Time complexity: $O(V + E)$, same as DFS.
• Implementation: Uses a queue (FIFO ordering is what ensures level-by-level exploration).
• Space complexity: $O(V)$ for the queue, but in practice BFS often uses more memory than DFS because it stores all nodes at the current frontier.
• Finds the shortest path in unweighted graphs. If every edge has equal cost, BFS guarantees the minimum number of steps to reach any reachable node.

---

Heuristic-Guided Search

These algorithms use domain knowledge to make intelligent choices about which paths to explore. Heuristics transform brute-force search into informed decision-making.

A* Search Algorithm

A* evaluates each node using the function:

$f(n) = g(n) + h(n)$

where $g(n)$ is the actual cost from the start to node $n$, and $h(n)$ is a heuristic estimate of the cost from $n$ to the goal. At each step, A* expands the node with the lowest $f(n)$ value.

• Guarantees the optimal path when the heuristic is admissible. A heuristic is admissible if it never overestimates the true remaining cost. For example, straight-line distance is admissible for road navigation because you can never drive a shorter distance than a straight line.
• Time complexity varies with heuristic quality. A perfect heuristic (one that exactly predicts remaining cost) leads to near-linear time. A poor heuristic causes A* to explore many unnecessary nodes, degrading toward BFS-like performance.
• Uses a priority queue to always expand the most promising node next.

---

Quick Reference Table

---

Self-Check Questions

1. Which two search algorithms both require sorted data but use different strategies to estimate target position? How do their best-case complexities compare?

2. You need to find the shortest path between two nodes in an unweighted graph. Which algorithm guarantees the optimal solution, and what data structure does it use?

3. Compare DFS and BFS: they share the same time complexity, so what factors should determine which one you choose for a given problem?

4. A question presents a scenario where you must search an infinitely long sorted stream of data. Which algorithm is designed for this situation, and why does it outperform standard binary search here?

5. Explain why A* search can outperform BFS on weighted graphs. What property must the heuristic function have to guarantee A* finds the optimal path?