Practical search method

I have a database of about 500,000 companies. For someone to interact with my app, they will do a search for a particular business. What is the most practical search method to account for misspellings, typos, etc. If I do an exact search (=) it is too restrictive and requires an exact match, a like search is also a form of exact match in that if someone leaves out an apostrophe or mistypes one character, it will miss also. I have also tried converting names and search terms to a phonetic search and then doing a like search but that returns way too many results especially for short names or names that are partially typed in.

Is there something in the middle? I like the way does it in their search box where for each character you type in they give you a list of 10 results, I assume the list is based on the most commonly searched of the possible results. How do they do that? Is that just powerful servers or is it an implemented search engine technique?