Change href value using jQuery

How do I rewrite an href value, using jQuery?

I have links with a default city

<a href="/search/?what=parks&city=Paris">parks</a>
<a href="/search/?what=malls&city=Paris">malls</a>

If the user enters a value into a #city textbox I want to replace Paris with the user-entered value.

So far I have

var newCity = $("#city").val();