Motion estimation plays an important role in video compression systems, and it's the most intensively computational and the most time-consuming part at the same time. So it could significantly affect the operation efficiency of whole video coding systems and the reconstructed quality of video sequence. The latest video coding standard, H.264, provides a significant coding efficiency than previous standards. But this coding gain comes at the cost of a very computationally-intensive motion estimation module. To realize the implementation of the H.264 video coding in-time, it's desirable to develop fast motion search algorithm. In order to reduce computation complexity of the motion search at sub-pixel accuracy, a fast and effective search algorithm for half-pixel motion estimation is proposed in this paper. Based on the single valley characteristic of half-pixel error matching function inside search grid, half-pixel candidate points needing checking are predicted with the help of comparison results of SAD values for four integer-pixel points around integer-pixel motion vector, so a great number of computations associated with search process are avoided. The experimental results reveal that, to all kinds of video sequences, the proposed algorithm can obtain almost the same video quality as that of the half-pixel full search algorithm with reduced average 72% computation cost.