If you know about the distribution of keys you can do even better by factoring that knowledge into where you split.