Daha önce kullanmadım fakat Mapbox'a bir bakmanı tavsiye ederim. Altyapı olarak OSM(Open Street Map)'ı kullanıyor sanırım. Belli bir kullanıcı limitine kadar da ücretsiz olduğunu söylüyor. Bir çok özelleştirme seçeneği ve plugin desteği de sunuyor. Dökümantasyonu da gayet geniş.

Aradığın search işlemini de bu link den yararlanarak yapabilirsin. Örneğin linkteki API'a search string'in ile istekte bulunursun, bu istek sonucu gelen json datasından istediğin koordinatları oluşturduğun haritanın koordinatlarına uygularsın. Yada Mapbox'un kendi arama kutusu özelliğini aktif edersin (o da şu linkten) o kadar uğraşmana gerek kalmaz.