Zwei Möglichkeiten, das Suchverhalten zu verbessern:
a) Verwende eine andere Datenstruktur.
b) Verwende eine Hilfsstruktur, die die Suche beschleunigt.
Ich würde Dir Skiplisten oder Hashmaps empfehlen. Für Beides findest Du in der
DP 
Code-Beispiele (Ich würde nicht darauf setzen, das eine Binärsuche das Non-Plus-Ultra ist).
Mir fällt ürigens kein Grund ein, bei einer sortierten Liste zu bleiben.