Комментировать

>Это сработает примерно со

>Это сработает примерно со скоростью O(n)
В расчете на все m элементов из b. Поэтому b не должен быть слишком маленким. Лично у меня m>>n.

>Но мне кажется интересным такой вариант (при сравнительно небольших m): первые фазы бинарного поиска делаются делением на мультипроцессоры:

Я думал над таким вариантом; это не очень выгодно, дело в том что уже при первой проверке в бинарном поиске отсекается половина элементов.
Нет, все же лучше работать с массовыми запросами.
Если в программе это не так, значит нужно снова продумать архитектуру программы и все же добится перехода от одиночных запросов к массовым, хотя бы и буферизацией.