Adding a taxonomy drop down to drupal search
I think you will need to use custom search module. For auto-complete feature i think it is better to go with custom development rather than depending on contributed modules which will come with lot of unwanted features. 

To preface :

You will need to use hook_form_alter() for add you custom field. 
Then with the help of hook_search you can inject your custom search criteria using search query extract and search query insert.