How do I find nearby app users in android?

To find nearby users efficiently, you need a spatial index. See: Hierarchical Triangular Mesh.

You also can use one of the databases that support spatial queries.

I'll probably send latitude and longitude information or address information to the server. Can't I compare those strings with all users' address list from the first numbers or letters using string searching algorithms or something?

That won't work with latitude and longitude because that way you can only search for proximity in one dimension. For example, 30°N 30°E will appear closer to 30°N 90°E than to 31°N 30°E.

It may work with addresses, but only if they are reliably connected with coordinates (i.e. not typed in by users), and only if you don't mind that users 200 meters apart but on different sides of some administrative border will not count as close to each other.