In this study, the authors propose an efficient fractional pixel search algorithm for H.264/AVC video coding to reduce the computational complexity in half/quarter-pixel motion estimation. A prediction for the optimal motion vector is derived under the assumption that the sum of absolute transform differences error surface is a symmetric parabolic function. With the optimal region, a decision rule for half-pixel search is proposed. The experimental result shows that approximately two search points are required. Based on the half-pixel search, a hierarchical quarter-pixel search is described and an extra three search points, on average, are consumed for each quarter-pixel search. Experimental results show that significant reduction in computation can be achieved, while maintaining high coding efficiency.