Алгоритмы запроса диапазона на целые потоки

Question

Я получаю поток положительных целых чисел в моей программе. Я должен хранить их по мере их получения и иметь возможность отвечать на запросы, находящиеся между ними.

Простое решение, которое пришло мне в голову, - хранить целые числа в хеш-таблице, где ключи являются символьным представлением целых чисел (ключи должны быть строками в моей хеш-таблице). Затем, всякий раз, когда приходит запрос диапазона [a, b], я могу просто перейти от a к b, проверить, существует ли ключ, и получить значение, если оно есть. Тем не менее, я не уверен, что это хороший подход.

Какие другие альтернативные решения существуют для этой проблемы?

Answer 1

Если вы сохранили упорядоченный список целых чисел из потока, считанного до сих пор, то запрос диапазона можно выполнить, найдя a (с использованием бинарного поиска) и итерации с этого момента, пока вы не пройдете b, так что время, потраченное на запрос, будет пропорционально фактическому размеру результата, независимо от того, насколько разреженным заполнен диапазон.