>эффективнее будет динамически растущий массив с бинарным поиском по нему
Спорно. Поиск по сбаллансированному дереву эффективней бинарного поиска по отсортированному массиву. А в моем случае дерево создается один раз, для последующего многократного поиска. Даже ради небольшого выигрыша в эффективности поиска готов жертвовать медленной инициализацией.
Насчет правильного обхода массива понятно. Я подумал, что может существовать какой-то эффективный алгоритм добавления элемента, если мы знаем, что он больше всех предыдущих, но, похоже, я ошибался.
