This algorithm has $O(n^2^)$ time and space complexity.

h2. Bidirectional search
 
bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.
 
!blog/meet-in-the-middle?12fig26.gif!
 
The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ nodes.
 
A better solution starts from both nodes and sees when the two search spaces meet.  This reduces the number of states explored to $O(p^k/2^)$.
 
The approach works well with both path finding problems on explicit graphs and with implicit state graphs like the ones you find in games.
 

h2. Breaking 2DES
!<blog/meet-in-the-middle?2des.png 70%!

The algorithm takes $O(sqrt(n))$ space and $O(sqrt(n))$ time.

h2. Bidirectional search
 
bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.
 
!blog/meet-in-the-middle?12fig26.gif!
 
The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ nodes.
 
A better solution starts from both nodes and sees when the two search spaces meet.  This reduces the number of states explored to $O(p^k/2^)$.
 
The approach works well with both path finding problems on explicit graphs and with implicit state graphs like the ones you find in games.
 

h2. Caveats
Unlike divide and conquer meet in the middle can't be applied recursively because the sub problems don't have the same structure as the original problem.