A phase-searching look-up table (PS-LUT) method is proposed to dramatically reduce the memory size of the new look-up table (N-LUT) method as well as to keep its advantage of fast computational speed. Small quantities of samples are chosen as the basic phase points (BPPs) in the principle fringe pattern (PFP), and phases of the object points for BPPs are precalculated and stored in the table. The phases of object point for the whole PFP could be quickly obtained through a phase-searching method. With proper reference beam phases, PFP could be rapidly generated. The experimental results reveal that the computational speed of the proposed method is about 24 times faster than that of the ray-tracing method, and the required memory size is 1731 times less than that of the N-LUT method. To eliminate the coherent noise of the N-LUT and PS-LUT, the random PFP N-LUT (RN-LUT) and PS-LUT (RPS-LUT), in which the PFP is randomly chosen for every object point, are put forward. The reconstructed images with a spatial light modulator indicate that both the RN-LUT and RPS-LUT methods are extremely effective in improving the quality of the reconstructed images.