Доброго всем дня.
Имеется ассоциативный массив: номер - значение. Элементы массива отсортированы по возрастанию номера. Задача простая: найти элемент с нужным номером и взять его значение.
Первое, что приходит в голову - использовать бинарный поиск. Но вот что смущает. К примеру, есть массив:
100 - 1
101 - 2
102 - 3
200 - 4
201 - 5
Нужно получить значения двух элементов: 101 и 102. Бинарным поиском находим 101. Следующим запросом нужно найти 102. Опять делать бинарный поиск. Но нельзя ли сделать быстрее: мы только что нашли 101 и знаем его индекс. Массив отсортирован по возрастанию, значит, 102 где-то рядом (номер-то не сильно отличается от уже найденного). Обязательно ли использовать бинарный поиск или есть механизмы, оптимизирующие поиск?
Однако если нужно получить 102 и 200, то скорее всего придется использовать поиск 2 раза, т.к. номера различаются значительно, хотя и находятся рядом.
Реализация будет проводится на Turbo Pascal (он еще жив :) ).

(0) номер всегда int ?
номера уникальны?

(1) Номера числовые, уникальные, целые, положительные.

(2) тогда
1) результаты всех поисков в кэш.
2) поиск ведется по диапазону который вычисляется с учетом кэша.

Индекс (дерево) не пригодится? (правда, придется потратиться на его создание).

>>Реализация будет проводится на Turbo Pascal (он еще жив :) ).


Пишу из под стола. Вы меня убили!

(3) Думал про кэш. Но тогда придется делать поиск уже по 2 массивам: кэшу и основному (если не нашел в кэше). Будет ли это быстрее?
Стал думать в сторону запоминания индекса последнего найденного элемента, вычисления расстояния до элемента, который надо найти и выбора: то ли делать поэлементный перебор от последнего, то ли бинарный поиск, если это расстояние превышает некоторый критерий.
(4) С деревьями ни разу не работал (увы). Хотя... всегда приятно освоить что-то новое.
(5) Это программа для промышленного контроллера. Там операционка, совместимая с ДОС6.2.

(6) если исходный массив много больше кэша - будет быстрее - кэш можно ограничить в размере

(0) да не парься ты. пускай каждый раз ищет. комп то небось не 286

(8) 40МГц

(9) всё равно не парься. бинарный поиск это хорошо.

Можно искать по части массива
Например нашли 101, а теперь ищем 110, тогда искать надо в подмассиве справа длиной не более 110-101=9 элементов

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

(11) читай (3)

(11) Вот я тоже в этом направлении соображал. Видимо нужно будет определить максимальное расстояние, до которого стоит использовать перебор (как вправо, так и влево).

(14) а элементов в массиве сколько?

если второй номер больше предыдущего - ищи в диапазоне (номер+1)-конце массива.
Если меньше - начало-(номер-1)

(15) Пока от 100 до 300. В будущем возможно будет и больше.

А соответствие вам не подойдет? вместо массива?

(18) а блин. это же паскаль.

(17) фи. это же фигня. чо прям тормозит на 300 элементах, что ты так озаботился? чота не верится.

ну будет у тебя допустим 10000 элементов, создай индекс с указателем на каждый сотый элемент. ищи сначала в индексе, потом в массиве. фигня короче. деревья еще какие то выдумал...

(17)
От 100 до 300 на современных компах не будет тормозить, даже если ты будешь делать линейный поиск на каждый поиск.
С кэшем поисков не майся - усложнение логики и доп.расход памяти сведёт на нет всю выгоду. Только если заведомо будешь знать, что 90% поисков будут рядом (кстати, как определить "близкость" двух поисков - та еще задача).

(6) Можно простой вариант (АВЛ-дерево)
https://ru.wikipedia.org/wiki/АВЛ-дерево