In H.264 video coding standard, in order to get higher compression ratio, HEXBS algorithm is employed to motion estimation, but the calculation work is very large. Compared with Full Search algorithm, it reduces the searching time obviously, but it takes fixed module and fixed searching step, which doesn’t take full advantage of center-bias characteristic of video sequence. Based on this observation, this paper proposes a new search algorithm named Rectangle search Algorithm, and the search algorithm is adaptive. At the end of the paper, the proposed algorithm has been experimented．The results show that the searching speed has largely increased while maintaining the same quality of image.