Every popular search interface has an "Advanced Search" page, where the user can make use of those search features which are rarely needed but then very important: title search, expression search, similarity search etc. MediaWiki supports these features and some more, but offers no help to the user to actually find them. If he is lucky, the wiki has a help page on searching which is linked from the search page, and he only has to read three or four pages of text to find out that which would be obvious on the first blink in a well designed form. If he is out of luck (such as in the case of trying to search the English Wikipedia), he will probably find Google (which has an easy to discover advanced search page, with domain restriction options) more useful, which is a bit of a shame.
In other words, the current implementation of advanced search (which is just a namespace selection) sucks horribly. It should have text fields like "search for pages with this words in the title" and "search for this expression", and everything that cannot be easily formulated as an additional text field (such as the * wildcard) should be explained in the search interface in an easily disoverable and understandable way.