If you're interesting in seeing how zipcodes are laid out in the use, Ben Fry has put together Zipdecode, a fun little zipcode mapping tool. Just start typing and interactively map zipcodes that match the partial zipcode as you type it.
All of the above are good examples of how to perform fast searching using an identifier instead of geographic coordinates. This works because the postal service has already assigned zipcodes to all addresses.
What if you start with a coordinate (lat,long) and want to compute the zipcode? Easy, just download the boundary files for zipcodes and find the one that contains your point, right? Well, not exactly. The following statement from the Census Bureau states the problem concisely:
The Census Bureau does not have maps or digital files showing the boundaries of U.S. Postal Service ZIP Codes. The fact that ZIP Codes aren't required to be polygons makes them difficult to map. They are networks of streets served by mail carriers or just individual post offices and are a tool for mail delivery. They also change periodically as required to meet Post Office operational needs. Various companies have created maps by interpolating boundaries between occurrences of ZIP Codes on the ground. However, this does not guarantee that the U.S. Postal Service delivery routes will follow this interpretation.
Census Zip Code Information
To help overcome these limitations, Census developed Zip Code Tabulation Areas.
ZCTAs are generalized area representations of U.S. Postal Service (USPS) ZIP Code service areas. Simply put, each one is built by aggregating the Census 2000 blocks, whose addresses use a given ZIP Code, into a ZCTA which gets that ZIP Code assigned as its ZCTA code. They represent the majority USPS five-digit ZIP Code found in a given area. For those areas where it is difficult to determine the prevailing five-digit ZIP Code, the higher-level three-digit ZIP Code is used for the ZCTA code.If you're interested in seeing how ZCTAs are laid out, take a look at an interactive ZCTA map. It's a nice mashup of a ZCTA map with Google Maps.
If you look closely, you will notice that holes exist in rivers and likely other places. This is a problem if you're trying to develop an indexing scheme, unless you don't need 100% coverage. However, if there is no census data there, it's likely that you will find anything of interest.