That will be tricky specially with making the whole thing responsive. The header will get crowded with menu, logo along with search bar and we need to align it all right. Can you consider placing the search widget on the top of the sidebar of each post/page instead? Unless your users rely very heavily on search, that should do IMO.
You can place search code anywhere you want as explained here – http://codex.wordpress.org/Function_Reference/get_search_form.
And you will need to modify the header.php for this.