The embodiments disclosed herein relate to the construction of a search space for determining a motion vector for a current block of a picture in a video sequence. The search space construction is split into in two main stages, wherein a first and a second partial search space are respectively determined. Based on an initial estimate of a motion vector, a first search space is first constructed. A first and a second candidate motion of the first search space are identified according to a cost function. Based on the first and the second candidate motion vectors, a second search space is constructed. The motion vector for the current block is selected from the candidate motion vectors of the first search space and the second search space.