Patent Document ID: 20120110049
Application ID: 12944350
Patent Flag: 0

Claim One:
1. A circuit configured to perform a search for a key in a sorted list of entries using a plurality of binary search iterations, comprising a plurality of binary search pipeline stages configured in a pipeline, each pipeline stage comprising: memory storing an orthogonal subset of the entries relative to the subsets of the entries in the memories of all others of the pipeline stages, the memory in each successive pipeline stage having exponentially more storage capacity than an immediately previous pipeline stage and including entries corresponding to a particular one of the binary search iterations; and comparison circuitry configured to compare the key to a particular entry stored in the memory of the pipeline stage, generate a comparison result, and pass the key and the comparison result to the immediately subsequent pipeline stage, the comparison result indicating whether the key is greater than or equal to, or less than the particular entry to which the key was compared, the comparison circuitry also being configured to select the particular entry to which the key is compared with reference to the comparison result received from the immediately previous pipeline stage.