In reply to Xharlie:
I have tried a few and settled back on OsmAnd. Mapfactor Navigator was OK, and might be worth a try.
With OsmAnd, think the internal data model for addresses is ... unusual. And not helped by the slightly odd data model OSM has. I've added Code Point Open postcode centroids on my phone, which helps a lot when searching for addresses. I look up the postcode, then zoom in enough to see street names and house numbers. Then pan around looking for probable parking places. The process is rather awkward though.