We present a novel fractal encoding method, based on a full-binary-tree searchless iterated function system (FBSIFS), that encodes image range blocks based on a fixed-location domain block. This algorithm is capable of encoding much smaller range blocks than traditional fractal algorithms, extending to 2×2 and 2×1 range blocks or even single image pixels. The FBSIFS method employs a rectangular block decomposition, similar in nature to the more general horizontal-vertical partitioning scheme. However, the proposed method has a simpler structure, similar to quadtree partitioning. Experimental results show that this algorithm is capable of providing superior performance, in terms of encoding time, compression rate, and reconstructed image quality, to traditional search-based fractal methods. The searchless binary-tree partition method also has better performance than searchless quadtree partition methods. A comparison with existing search-based and searchless fractal algorithms is presented, including compression rate, peak SNR of the reconstructed image, and algorithm complexity. A JPEG comparison is also presented.