Just a simple note: "in C++11, newly inserted elements follow their equivalents already in the container."
Thus, when nums[i] == *mid, we do not need to decrease mid, since nums[i] will inserted after mid.
This point was bothering me until I read your post, apparently this is quite different from the case before C++ 11!
"In C++ 98: There are no guarantees on the relative order of equivalent elements."
Interestingly, when I replace lower_bound with find in the code, it still passes OJ. I couldn't find any info on which of the equivalent elements would find return, but looks like it's returning the first element if find can be used interchangeably with lower_bound in this case?