I have the following dilemma: I have a list of strings, and I want to find the set of string which start with a certain prefix. The list is sorted, so the naive solution is this:

Perform binary search on the prefixes of the set, and when you find an element that starts with the prefix, traverse up linearly until you hit the top of the subset.

This runs in linear time, however, and I was wondering if anyone can suggest a more efficient way to do it.