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?
what I would do is divide the search range into 3150 blocks of subranges, organize them randomly, and look for h160 prefixes equivalent to the prefix in question (the hash160 that produces the address with the prefix "1PWo3JeB9jr"), I search the blocks sequentially and each time I find the match of the prefix I save the remaining range of the block in a txt, and discard said block, in 60:80% of the cases, you will not need to review the . txt, in the worst case (when your target is in the same block where statistically there should only be 1 "1PWo3JeB9jr" and that coincidentally is after the first "1PWo3JeB9jr" which is not the target within the same block, you will have to go to the TXT (as you will see a series of unlikely things must happen for you to need the txt). Therefore, the probability of finding it with less effort than traditional sequential brute force is higher.
but the effort you would make if the worst case scenario happened as a consequence would be equal to searching the entire range in the traditional way.