The reconstructed image of probabilistic visual cryptography (VC) is inevitably accompanied by the loss of secret image information and degradation of visual quality. Since halftone technique can realistically simulate grayscale continuous tone image with a binary image, in this paper, by combining VC sharing with grayscale image halftone technique, we propose a probabilistic VC scheme for grayscale image using EDBS (Efficient Direct Binary Search) to improve the quality of the reconstructed image. The probabilistic VC sharing is adopted into the EDBS halftone process, and the reconstructed image is taken as the optimization object. Through local optimizations and global iterations, the optimal reconstructed image is finally achieved under the established optimization strategy. Theoretically the proposed scheme possesses the same security strength as the traditional VC and experimentally the comparative analysis verifies the effectiveness of this scheme.