Wenn selten die selben Zahlen abgefragt werden, würde der Cache immer größer werden.
Da ist dann so ziemlich die schlechteste Lösung.
Nicht wirklich. Der Cache kann auch nicht größer werden als das anfangs initialisierte Array/Dictionary für alle möglichen Abfragewerte.
Deshalb halte ich auch den Vorschlag von TigerLilly für nicht so sinnvoll, wenn der Zahlenbereich sehr groß ist oder gar Kommazahlen oder Zeitstempel enthält. Bei der Abfrage ist das zwar die schnellste Lösung, aber nur wenn das Ergebnis bereits vorab ermittelt wurde. Genau das wollte der TE aber optimieren. Die Bildung einer Liste von Intervallen ist auch nicht aufwendiger und bei der Abfrage fast genauso schnell. Es wird weniger Speicher benötigt, was den Cache entlastet und so auch zur Geschwindigkeit beiträgt. Aber die "Richtige Lösung" gibt es nicht.