Visual C++ :: Find Largest Value Smaller Than Key

I have a std::map<int, foo>

what's the ideal way to get an iterator to the item that has the largest key (int) smaller than a given value.

basically, the item before upper_bound(). I can use upper_bound() and then decrement, but it needs special cases for both end() and begin(), and in the case of end() I'm not sure how I get it to the last item in the map, afaik, we're not allowed to decrement end().

Code:
auto it = mymap.upper_bound(x);
if (it==mymap.begin()) // first item in the map is already too large. reject
NotFound();
else if (it==mymap.end())

[Code] .....

// here it points to largest item smaller than x.

I can iterate over the entire map and do a compare, but then I pretty much loose the benefit of the binary search.