The video stream represents the continuous and rapid flow of image files. The video coding performs the compression of both image and audio information. The video compression standards associated to ITU-T and ISO are MPEG-X and H.26X standards. The H.264/AVC is leading video compression standard and it has been adopted in many video coding applications. In order to compress the video for efficient transmission and storage, the redundancy among adjacent frames must be exploited. A frame is selected as reference and subsequent frames are predicted from the reference frame using a technique known as motion estimation. The purpose of achieving redundancy in motion compensated prediction is to find the best possible block matching without considering a large number of search points to minimize the compression efficiency. In this research work, two approaches concerned with the block matching for making easy of computation in finding the frame proposed on H.264/AVC. In the first approach, Adaptive Order Square Hexagon (AOSH) search algorithm was developed. In the second approach, Adaptive Order Cross Square Hexagon (AOCSH) search algorithm.