Bei der binären Suche ist es leider nicht so, das
cur am Schluss auf die richtige Stelle zeigt. Du musst noch prüfen, ob das einzufügende Element wirklich an die Stelle kommt. Der Rest sieht soweit ganz gut aus.
Für Deine Bedürfnisse bietet sich eine Hashmap an, die ist schneller. Fertiges Zeugs findest Du
hier.
Ein DAWG ist noch schneller, verbrät aber auch wesentlich mehr Speicherplatz.