Эффективный алгоритм для двустороннего поиска?
Зависит от того, сколько это "достаточно много" и сколько есть оперативной памяти под эту задачу (ПК, смартфон, эмбедед разработка?).
Если память позволяет, то самым быстрым будет два бинарных дерева (либо два сортированных массива-списка, но тогда после добавления элемента придётся пересортировывать или искать место вставки).
Если A и Value сами по себе большие и/или сложные объекты, которые нельзя продублировать, то можно сделать две индексных таблицы, ссылающихся на оригинальные данные. 
Самое быстрое - два отсортированных массива, в каждом из которых и А и Value.
Самое удобное, но чуточку менее быстрое - два бинарных дерева.
если заточены именно на скорость, то хранить дубли, это нормально.
то есть хранить все комбинации значений:
Ключ-Значение
А - value1
value1 -А