I did something like this a couple of years back, but in PowerBasic on a PC, for a similar number of addresses (vs the millions of addresses of the full country database). Somewhat embarrassingly, I can't find the program right now (I did find the database, though: was 3.6 million lines but just for the state).
Anyways, it was a ripper. What it would do is present an ever-shrinking list of addresses that contained/matched all of the words that you had typed in so far.
So let's say I was looking for 14 Zig Zag Road Belgrave and so far I had typed:
"14 Z"
then the program split that into space-separated words of "14" and "Z", scanned the list of 40795 addresses, and showed me the first dozen of the 22 addresses that had both those "14" and "Z" in it:
[1] 114 BLUE HORIZONS WAY, PAKENHAM 3810
[2] 14 AZURE COURT, PAKENHAM 3810
[3] 14 BRONZEWING STREET, PAKENHAM 3810
[4] 14 ELIZA HEIGHTS, PAKENHAM 3810
[5] 14 ELIZABETH COURT, PAKENHAM 3810
[6] 14 FITZROY STREET, PAKENHAM 3810
[7] 14 HAZELVALE ROAD, TECOMA 3160
[8] 14 JAZZ COURT, PAKENHAM 3810
[9] 14 MACKENZIE STREET, COCKATOO 3781
[10] 14 OZONE AVENUE, EMERALD 3782
[11] 14 TRIBUZI CLOSE, PAKENHAM 3810
[12] 14 ZENITH STREET, PAKENHAM 3810
which unfortunately doesn't show the address I'm looking for because it's further down the list, but... no worries, because by now I've pressed the "I" key and so my search text is "14 ZI" that the program splits into space-separated words of "14" and "ZI" and now the list of possibilities is reduced to:
[1] 14 MACKENZIE STREET, COCKATOO 3781
[2] 14 TRIBUZI CLOSE, PAKENHAM 3810
[3] 14 ZIG ZAG ROAD, BELGRAVE HEIGHTS 3160
and then when I press "G" = search text "14 ZIG" = words "14" and "ZIG" = one match
[1] 14 ZIG ZAG ROAD, BELGRAVE HEIGHTS 3160
Bingo!
The beauty of doing substring searches is that... well, let's take Mackenzie Street from above. There are at least 4 ways to (mis)spell that name: it could be "Mc" or "Mac", and with or without a space after the "c". But we can search for "14 KENZ" and we will find it, even though the "KENZ" is in the middle of a word.
Also, it is order-agnostic, so if you search for "Town1 Town2" then it will find both "Town1-Town2 Road" and "Town2-Town1 Road" (and also the local shorthands "Town1 Road" in Town2 and "Town2 Road" in Town1 - Bonus!)
On a Windows laptop, scanning through those 40795 addresses took < 2 ms, so speed wasn't an issue. It might be different on a phone.