In this paper, we propose a novel fast block matching algorithm design strategy based on the complexity-distortion optimization. The goal of our design is to achieve the maximum image quality under a target computational complexity and to provide a flexible fast block matching algorithm that allows user to terminate algorithm at any target computational complexity. Based on the proposed predictive complexity-distortion benefit list technique, which is employed to predict the motion compensation benefit, we modify the full-search block matching, three-step search, new three-step search, and four-step search to the flexible algorithm. Experimental results show that the flexible algorithms could achieve better performance than traditional fixed complexity algorithms from the viewpoint of complexity-distortion optimization.