Primal actually has pretty good search (this is from iOS test flight) 
Discussion
Interesting...
did you have a mutual friend / follower that already had me followed?
Amethyst, Iris, Plebstr, Nostrudel, pretty much all the good android + web options have awful search unless you are a massive account like nostr:npub1a2cww4kn9wqte4ry70vyfwqyqvpswksna27rtxd8vty6c74era8sdcw83a or nostr:npub1xtscya34g58tk0z605fvr788k263gsu6cy9x0mhnm87echrgufzsevkk5s
that can't be the standard if we want to make a serious push for new users
Primal has a caching server that calculates things like how many followers a person has and they use that to sort the search results. In nos.social we don’t, yet, have that, so we sort by mutual followers. Both do a great job at finding the right nostr:npub180cvv07tjdrrgpa0j7j7tmnyl2yr6yr7l8j4s3evf6u64th6gkwsyjh6w6 but overall popularity isn’t as good when you’re looking for your friend Matt. For new users who don’t have anybody then the overall popularity is better than mutual follows.
Coracle calculates and displays a kind of Web of Trust (WoT) score for each person which is nice.
All of which would be improved if we had a good way to say, this is the Matt who you’re following on twitter/mastodon/instagram or have the email / phone number of.
You don’t even need a central server to have good search. The damus profile database gets filled up with not too much use. 
k you have me though already followed?
I had a friend join NOSTR the other day through Damus I believe. She goes by @ RilezKirk
No posts yet
See if you can find the account via search and share the NPUB, I'll tell you if it's the right one
NONE OF the 8 clients I tried could find her
Right now most clients don’t use relays that host and share just contact and profile information. We were using purplepag.es by nostr:npub1l2vyh47mk2p0qlsku7hg0vn29faehy9hy34ygaclpn66ukqp3afqutajft until we added that functionality in to our own relay.nos.social. I think using those is a stop gap, but we need a better solution to finding people and contacts.
Primal runs its own caching and search relays to make the experience better. It’s written in Julia! That’s not a language I’ve come across since I was hanging out at MIT. We need multiple compatible services like what primal is doing.