One of my friends worked with David J. C. MacKay on Dasher: https://en.wikipedia.org/wiki/Dasher_(software)

I think that may already do what you want?

There are assistive typing devices that use complex models to predict characters: https://en.wikipedia.org/wiki/Dasher_(software)

The downside is that with a powerful enough model you could replace the patient with a coinflip and have a hard time telling the difference.

Is binary search really the most practical? Can most people answer questions like "Is P after M" without a lot of thought and counting out all the letters one by one starting at one of the input letters?

A basic markov chain predictor seems like it could work, if you had a short enough window to be sure it couldn't invent its own nonsense.