map::find with a type that's comparable but not convertible to key_type

std::map::find accepts const key_type& as an argument. This way it requires the argument to be convertible to key_type. That seems an oversight to me because the argument doesn't have to be convertible to key_type, it only has to be comparable to it.

I can make an arbitrary type comparable by defining two operator< overloads:

struct A;
bool operator<(const key_type&, const A&);
bool operator<(const A&, const key_type&);

map::find should itself be a template. But it's not. So now that I'm done whining I can ask the actual question: is there a way to easily work around this and search among map keys by a comparable but not convertible value?

My understanding is I could use std::find_if, but that would be linear search instead of binary search (O(n) instead of O(Log(N))). Naturally, I don't want to implement binary search by hand.