In the letter, we propose an improved histogram shifting (HS) based reversible data hiding scheme for small payload embedding. Conventional HS based schemes are not suitable for low capacity embedding with relatively large distortion due to the inflexible side information selection. From an analysis of the whole HS process, we develop a rate-distortion model and provide an optimal adaptive searching approach for side information selection according to the given payload. Experiments demonstrate the superior performance of the proposed scheme in terms of performance curve for low payload embedding.