Recently Microsoft released preview version of PowerApp Component Framework which enable developers working on Dynamics 365 to create cool custom controls and enhancing the capability.
I have Utilized it to create Address Finder control which should work for New Zealand region.
For this i have have used AddressFinder API which is a paid service but provides trial lookups also. You can login to their website and request for the key which suites your need.
You can find source code and solution file here
To configure, import AddressFinder.zip solution in your D365 environment.
After Publishing go to the form where you want to add this control. Select the field on which you intent to display the search box. Here I have used AddressLine_1. Configure the remaining fields in the control and add your Addressfinder key in Address Finder Key field
Right now there some issue with the form because of which address field are not showing up when you are trying to configure them in the custom control. You can follow this blog which will take you through how to add address fields to your custom control.