Replying to Brain Teaser from my boss

So my boss came in my office this morning and asked me a question and he wants me to have an answer tomorrow. He's big into "outside the box" thinking so I'd like to impress him on this one, and I have no idea how to answer it. +k for the help

In the 1980s, Microsoft used to ask employees this question on their application. What is the best and most efficient way on how to accurately guess how many names are in a New York City phone book? The pages are not numbered. Also remember that this is the 80s so the internet is not an option. Please help! Thanks