Из какой коллекции можно быстро удалять элемент, но к ней применим бин. поиск?
TreeSet.

Там можно искать нужный вам элемент через floor или ceiling. Поиск и удаление, если создатели библиотеки в java хоть что-то слышали про алгоритмы и структуры данных, работают за логарифм.
Написать своё сбалансированное дерево. Удаление и upperBound будут за логарифм