Your best bet is to put the data in a spatial database such as PostGIS, and execute a spatial query that performs a nearest neighbour search.
From http://boundlessgeo.com/2011/09/indexed-nearest-neighbour-search-in-postgis/:
PostGIS (the development code in the source repository) now has the ability to do index-assisted nearest neighbour searching... You will need PostgreSQL 9.1 and the PostGIS source code from the repository, but this is what a nearest neighbour search looks like:
SELECT name, gid FROM geonames ORDER BY geom <-> st_setsrid(st_makepoint(-90,40),4326) LIMIT 10;
Note the magic <-> operator in the ORDER BY clause. This is where the magic occurs. The <-> is a “distance” operator, but it only makes use of the index when it appears in the ORDER BY clause. Between putting the operator in the ORDER BY and using a LIMIT to truncate the result set, we can very very quickly (less than 10ms on a 2M record table, in this case) get the 10 nearest points to our test point.
There are spatial databases for Android such as Spatialite if you require the data to be stored locally.