...
Tertiary search would be similar to binary search, except instead of just using the "left" and "right" keys, a user could also use the "down" key. This would require only three key presses for each letter. A space could no longer be the "down" key and would likely be simply appended after "z" ie. hitting "right" three times. This would not be obvious to a user, and would have to be indicated somehow, perhaps a note that says "Hit right three times to enter a space" which would still bring the user through the visualization as if they were choosing the letter after "z".
Autocomplete
This binary search could encompass an autocomplete as pictured below. At any point, if the user's selection shows up in the list, they could hit the "down" key to select from a list selections. 