Algorithms
Advanced Search Algorithms
Difficulty: Advanced
Plain BFS finds the shortest path through a 1000x1000 grid by exploring outward in concentric circles, examining about a million cells. A with a Manhattan-distance heuristic walks almost straight to the target and examines a few thousand....
Advanced Search Algorithms
Plain BFS finds the shortest path through a 1000x1000 grid by exploring outward in concentric circles, examining about a million cells. A* with a Manhattan-distance heuristic walks almost straight to the target and examines a few thousand. Both algorithms use the same priority-queue framework; the only difference is that A* adds a heuristic estimate to the cost function and biases the search toward the goal. That single addition is what powers GPS, game-pathfinding, and motion planning in robotics.
Advanced Search Algorithms covers the search refinements that go beyond plain BFS and DFS. You will implement A* with the f(n) = g(n) + h(n) cost function, derive what makes a heuristic admissible, and prove the optimality guarantee under admissibility. Bidirectional search runs BFS from both source and target until the frontiers meet, cutting O(b^d) to O(b^(d/2)). Iterative Deepening DFS combines BFS-style completeness with DFS-style O(d) memory, using repeated depth-limited DFS. The lesson finishes with two specialized array searches: Jump search at O(sqrt(n)) for sorted arrays where binary search is awkward, and interpolation search at O(log log n) expected for uniformly distributed keys.
In BFS & DFS (Intro), you wrote the basic skeletons. Graph Algorithms (Core) introduced Dijkstra's priority-queue relaxation, which A* generalizes by adding the heuristic.
Next, Game Theory turns to two-player adversarial search.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement A* search with an admissible heuristic and explain why admissibility guarantees optimality.
Apply Bidirectional BFS to reduce search space and detect the meeting point between two frontiers.
Implement Iterative Deepening DFS and analyze why repeated work does not significantly increase total cost.
Implement Jump Search on a sorted array and explain its O(sqrt(n)) complexity.
Describe Interpolation Search and when it outperforms binary search.
Why This Matters
01
A* search is the backbone of pathfinding in games, robotics, and GPS navigation -- it guarantees optimal paths while exploring far fewer nodes than BFS by using heuristic guidance.
02
Bidirectional BFS reduces the search space from O(b^d) to O(b^(d/2)), which can be the difference between a solvable and unsolvable problem in practice.
03
Iterative Deepening DFS achieves BFS-level completeness and optimality while using only O(d) memory, making it ideal for large search spaces where BFS would exhaust memory.
04
Understanding when to apply each search strategy is a key skill for both competitive programming and real-world system design.
Key Terms
7 terms you'll encounter in this lesson
Heuristic Function h(n)
An estimate of the cost from node n to the goal. A* uses this to prioritize which node to expand next. The function must never overestimate the true cost (admissible) to guarantee optimal solutions.
Admissible Heuristic
A heuristic that never overestimates the true cost to the goal: h(n) <= actual cost for every node n. Examples: Manhattan distance and Euclidean distance for grid pathfinding.
f(n) = g(n) + h(n)
The evaluation function in A*. g(n) is the known cost from start to n, h(n) is the estimated cost from n to the goal. A* always expands the node with the smallest f(n).
Bidirectional BFS
A search that runs BFS simultaneously from both the start and the goal, meeting in the middle. Reduces time from O(b^d) to O(b^(d/2)) where b is the branching factor and d is the depth.
Iterative Deepening DFS (IDDFS)
A strategy that runs depth-limited DFS repeatedly with increasing depth limits. Combines BFS completeness with DFS space efficiency. Time is O(b^d), space is O(d).
Jump Search
A search on sorted arrays that jumps ahead by sqrt(n) blocks, then performs linear search within the block. Time: O(sqrt(n)). A middle ground between linear and binary search.
Interpolation Search
A search that estimates the position of the target using value interpolation rather than always halving. Achieves O(log log n) for uniformly distributed data but O(n) in the worst case.
Heads Up
Common misconceptions to watch out for
"A* always explores fewer nodes than BFS"
A* explores fewer nodes only when the heuristic is informative. With h(n) = 0 for all nodes, A* degenerates to Dijkstra's algorithm. The quality of the heuristic determines the speedup.
"Iterative Deepening wastes too much work by re-expanding nodes"
Because the number of nodes at depth d dominates the total (it grows exponentially), the repeated work from earlier depths adds only a constant factor. The total time is still O(b^d), the same as BFS.
"Bidirectional BFS always halves the search depth"
Bidirectional BFS works well when the graph is undirected or when you can efficiently reverse the goal direction. For directed graphs with no easy reverse, it may not be applicable.