Adaptive out-of-service search behavior by a wireless user equipment (UE) device. The UE may perform cellular communications according to a radio access technology (RAT). It may be determined that cellular service according to the RAT is not available. A search algorithm may be selected from at least two possible search algorithms. A search for cellular service according to the RAT may be performed according to the search algorithm. The various possible search algorithms may specify different ratios of time spent scanning for cellular service to time spent sleeping. The selected search algorithm may be chosen based on any or all of an estimated remaining battery life of the UE, a user activity level, user input, or various other considerations.