What is the best data structure to store contact information [name , phone number]?
Trie can be useful to search a phone number when name is given.
What if I want to find a persons name given his phone number. i.e. how can I find name when I know the phone number?
Is trie efficient for such search?
Yes, a trie is good. Instead of using the characters in the string as the key at each level, you can use the bits in the phone number (if you are storing them as integers). For speed reasons, you might decide to use 3 or 4 bits at a time.
This would work by having a trie struct that stores the current identity information and then an array of pointers to child trie structs.
struct phone_number_trie {
struct contact_info *info;
struct phone_number_trie *children[4]; // or 2, 8 or 16 etc.
};
E.g. storing the phone number '83' (which is 1100011 in binary) in a tree where the root is root, you might mask the lower 2 bits (e.g. & 3), which are 11, so you would recurse down into root->children[3] with the remaining bits of the phone number 11000 (i.e. shift it right 2). The next indices would be 0, and then 10 and then 1 (so you would be pointing at root->children[3]->children[0]->children[2]->children[1]). At this point you have no set bits left in your phone number, so you've found the right place to insert.
(You could also consider using a Patricia trie, but this is significantly harder to implement.)