Быстрый поиск подходящего значения

Добрый деньЕсть двухсвязный список каждый элемент которого имеет целое значение (ключ). Задача: как можно быстрее найти любой элемент со значением меньше заданного порога N. Список может меняться от одного поиска ко другому, однако N (порог) может только увеличиваться при следующем поиске. Критично по скорости, так что "no containers/STL etc. please"Спасибо