As a fast search algorithm for motion estimation, the unsymmetrical-cross multi-hexagon-grid Search (UMHexagonS) is widely used in H.264. However, the research found that there were some shortages in this algorithm, such as the computational complexity. Based on this, we improve the UMHexagonS algorithm to reduce the computation. By partitioning the search range, we can only search the prediction range to get the best motion vector with the other range ignored. The simulation shows that the improved algorithm can obviously reduce the search time, while its coding quality is almost the same as that of the original algorithm. It can get a very good tradeoff between the search time and the coding quality.