The challenge of large-scale content-based image retrieval (CBIR) has been recently addressed by many promising approaches. In this work, a new approach that jointly optimizes the search precision and time for large-scale CBIR is presented. This is achieved using binary local image descriptors, such as BRIEF or BRISK, along with binary hashing methods, such as Locality-Sensitive Hashing and Spherical Hashing (SH). The proposed approach, named Multi-Bin Search, improves the retrieval precision of binary hashing methods through computing, storing and indexing the nearest neighbor bins for each bin generated from a binary hashing method. Then, the search process does not only search the targeted bin, but also it searches the nearest neighbor bins. To efficiently search inside targeted bins, a fast exhaustive-search equivalent algorithm, inspired by Norm Ordered Matching, has been used. Also, a result reranking step that increases the retrieval precision is introduced, but with a slight increase in search time. Experimental evaluations over famous benchmarking datasets (such as the University of Kentucky Benchmarking, the INRIA Holidays, and the MIRFLICKR-1M) show that the proposed approach highly improves the retrieval precision of the state-of-art binary hashing methods.