Focusing light inside scattering media in a freely addressable fashion is challenging, as the wavefront of the scattered light is highly disordered. Recently developed ultrasound-guided wavefront shaping methods are addressing this challenge, albeit with relatively low modulation efficiency and resolution limitations. In this paper, we present a new technique, time-reversed ultrasound microbubble encoded (TRUME) optical focusing, which can focus light with improved efficiency and sub-ultrasound wavelength resolution. This method ultrasonically destroys microbubbles, and measures the wavefront change to compute and render a suitable time-reversed wavefront solution for focusing. We demonstrate that the TRUME technique can create an optical focus at the site of bubble destruction with a size of similar to 2 mu m. We further demonstrate a twofold enhancement in addressable focus resolution in a microbubble aggregate target by exploiting the nonlinear pressure-to-destruction response of the microbubbles. The reported technique provides a deep tissue-focusing solution with high efficiency, resolution, and specificity.