You can try to search-as-you-type on our hacker news search to see the difference with other search engines: http://hn.algolia.com/

You have relevant results after each keystroke, even with typos. Classical engines use approximation to perform instant search, like the suggest module of Elasticsearch.