UMHexagonS is the fast integer motion estimation algorithm adopted in H.264/AVC. It shows very good capability in both reducing motion estimation time and keeping rate distortion performance from QCIF format to HD format. With an averaging 0.05dB PSNR loss and only one case up to 0.1dB, more than 90% time reduction can be achieved by UMHexagonS compared with FFS. However, fixed search range is used in UMHexagonS. By adjusting search range dynamically, motion estimation efficiency can be improved greatly. Based on the new strategy of combining UMHexagonS and some dynamic search range algorithm, two new dynamic search range algorithms, NDSR, PDSR, thus, two new fast integer motion estimation algorithms, NDSR+UMHexagonS, PDSR+UMHexagonS, are proposed in this paper. Experiment results show that, compared with UMHexagonS, averaging 20% time reduction can be achieved with nearly no PSNR loss for the NDSR method, and averaging 50~60% time reduction can be achieved with averaging not more than 0.1dB PSNR loss for the PDSR method, which is very valuable to real-time applications.