This paper proposes an efficient search algorithm for high dimensional binary fuzzy databases that store songs or data with a similar structure. A song is represented by a high dimensional binary vector using the audio fingerprinting technique. Audio fingerprinting extracts from a song a fingerprint which is a compact signature that summarizes an audio recording. A song can be recognized by matching an extracted fingerprint to a database of known audio fingerprints. However, the nature of high dimensional binary data makes many modern search algorithms inapplicable. The high dimensionality of fingerprints suffers from the curse of dimensionality. In order to tackle this problem, we propose a new search algorithm based on inverted indexing, the multiple fingerprint match principle, the offset match principle, and the early termination strategy. We evaluate our technique using a database of 2,000 songs containing approximately 4,000 fingerprints and the experimental result shows encouraging performance.