CareerCup

What if someone wants to search by address or company name or any attribute other than name or number ?

I think we need to create trie. There will be contact object.
Contact {
String Name,
String lastName,
String companye,
int[10] phone,
int[10] mobile ...
String address( we can also create address object and add more details if we want)}

there will be seperate trie for each attribute pointing to this object. So phoneTrie, nameTrie,
..etc.
For every update/delete/insert these trie will be updated.

We create a tree data structure,
the tree is a general tree with at max 26 children, and
each node also store a bool variable(is used for telling weather number present here or not) and a string (used to tell contact number along with code number).
and choose child function(which uses char to identifies the children)
Here is insert methods

we start with root node, and move from root node to children's according to each char.
for example if user name is "sonesh", then from root node it go to "s"th children, then from "s"th node it go to "o"th children and so on.
when we reach to "h"th node, 
In this if at any point we does not get require children, then we create that children, and move to that children.
we set bool variable to true, 
and set string variable to sonesh's number.

Now we can easily able to extend it to have multiple contacts with same name, or we can easily able to restrict it, Here we can also consider "space" as a char.
Now get contact can also be implemented very easily,
Here both insert and get have constant complexity(O(1)).

use hash table and name as key.

I would generate integer ids for names and phone numbers that get entered into the mobile phone. (I know phone numbers are already integers, but the ids would be shorter.)

Then maintain two parallel maps:

name id -> phone number id
phone number id -> name id

You could implement the maps as hashes, or you could implement them as simple arrays and do binary search. If you go the array route (an array of tuples of ints), then lookups in both directions will be log N, displaying the contact list ordered by name will be O(N), and insertions/deletions/edits will be O(N), but you'll dealing with ints, so they'll be fast.

If you're mostly dealing with lookups, then a hash will be sufficient, but if you are frequently displaying contact names, then you'll want some sort of auxiliary data structure that has the names already in order (either explicitly via an array or implicitly via a binary tree).

Use Trie to store the names and the number as part of the last node in the trie. This way a prefix can get all the phone numbers.

Use a multimap

#include <map>

int main()
{
    std::multimap<string, int> myAddressBook;

    myAddressBook.insert( pair<string, int>("Bob", 5551212));
    myAddressBook.insert( pair<string, int>("Bob", 5551234));
    myAddressBook.insert( pair<string, int>("Jennie", 8275309));
    myAddressBook.insert( pair<string, int>("Sally", 5559873));

    std::multimap<string, int>::iterator it = myAddressBook.find("Jennie");

    std::cout << "Phone number for Jennie is" << it->second << '\n';
}

Tree maps can be used for this purpose.

TreeMap tm = new TreeMap();
// Put elements to the map
tm.put("John Doe", new Double(3434343434));
tm.put("Tom Smith", new Double(1232212322));
tm.put("Jane Baker", new Double(1378000823));
tm.put("Todd Hall", new Double(9922234567));
tm.put("Ralph Smith", new Double(1908123456));
// Get a set of the entries
Set set = tm.entrySet();
// Get an iterator
Iterator i = set.iterator();
// Display elements
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}

And to get a particular phone number:

System.out.println("John Doe's phone number is: " +
tm.get("John Doe"));

Use Suffix Trees...If you want that your search should continous stream with no delimiters,else use compressed tries.