Motion estimation plays a key role in a motion-compensated block-based hybrid DCT coding scheme. To speed up the computation of motion estimation, many fast search algorithms have been proposed. A recent one, called enhanced hexagon-based search (EHEXBS), focused on reducing the number of search points in a fine-resolution inner search after a low-resolution hexagonal search. In this paper, we propose a novel inner search algorithm, named efficient hexagonal inner search (EHIS), to further reduce the number of search points. In EHIS, we use the central minimal distortion information and exploit the distortion information of the points located on the hexagonal pattern. Experimental results show that EHIS performs better than the EHEXBS in terms of the number of search points or the mean squared error. In addition, EHIS omits the overhead of six additions in each EHEXBS.