Methods and systems for rate-constrained search ordering algorithms for reducing computational cost of motion estimation in video coding have been provided. Conventional search orderings, such as spiral search, can weaken the filtering criterion of rate-constrained successive elimination algorithms. Simulation results provided herein above demonstrate that, on average, the amount of SAD (sum of absolute differences) operations required to encode the tested sequences, is reduced using embodiments of the invention, when compared to the conventional implementations of spiral search for example. Advantageously, for sequences with unpredictable motion, this reduction may be greater than 5%, and may even exceed 10% when smaller block partitions are evaluated.