> Obviously a binary search can't do comparisons in parallel, though.
Sure you can, although at reduced efficiency the "deeper" you go.
For example, while searching a range of size N, you know your next probe point will be at N/2. You also know the probe point after that will be at N/4 or 3N/4, and so on. You know up-front all the possible probe points. Of course, only one out of the two probe points N/4 or 3N/4 or will actually be useful, depending on the N/2 result - but that doesn't stop you from comparing all three in parallel.
You can get a reasonable speedup this way: the extra comparisons happen in parallel and for a moderate depth the unnecessary probes are more than compensated by doing comparisons in parallel.
Sure you can, although at reduced efficiency the "deeper" you go.
For example, while searching a range of size N, you know your next probe point will be at N/2. You also know the probe point after that will be at N/4 or 3N/4, and so on. You know up-front all the possible probe points. Of course, only one out of the two probe points N/4 or 3N/4 or will actually be useful, depending on the N/2 result - but that doesn't stop you from comparing all three in parallel.
You can get a reasonable speedup this way: the extra comparisons happen in parallel and for a moderate depth the unnecessary probes are more than compensated by doing comparisons in parallel.