Say for puzzle 71 you started searching for the prefix 1PWo3JeB9jr.  There are ~ 3150 prefixes in the keyspace that start with 1PWo3JeB9jr and let's say you starting searching in the middle and found the first 1PWo3JeB9jr around 50%.

Break up the 71 keyspace into 3,150 blocks each with 750 Quadrillion keys each.

What if you made approximately 1570 (+750 quadrillion) jump points going up from the prefix 1PWo3JeB9jr and 1570 (-750 quadrillion) jump points going down from the prefix 1PWo3JeB9jr and then searched all those points simultaneously from the midpoints outwards?