The challenge of large-scale image retrieval has been recently addressed by many promising approaches. In this work, we propose a new approach that jointly optimizes the search accuracy and time by using binary local image descriptors, such as BRIEF and BRISK, and binary hashing methods, such as Locality Sensitive Hashing (LSH) and Spherical Hashing. We propose a Multi-bin search method that highly improves the retrieval precision of binary hashing methods. Also, we introduce a reranking scheme that increases the retrieval precision, but with a slight increase in search time. Evaluations on the University of Kentucky Benchmark (UKB) dataset show that the proposed approach greatly improves the retrieval precision of recent binary hashing approaches.