How a Phone’s Contact Search Finds Matches as You Type

The magic trick, and why it needs engineering

Search-as-you-type looks simple until you ask what the phone is really being asked to do. Every single keystroke is a new question. By the time you type the fourth letter of a name, the phone has answered four separate searches, and it has to finish each one before your finger lands on the next key. Usability researchers have used a rule of thumb for decades: if a response arrives in about a tenth of a second, people experience it as instant. Anything much slower and the interface starts to feel like it is lagging behind you.

Now picture the other side of the problem. A phone might hold a few hundred contacts, but plenty of people have thousands, once you count work contacts, old numbers and group chats. And each contact is not just a name. It has several numbers, an email, a nickname, a company. The search has to be fast, forgiving, and sensible about which result to put first.

I have built search boxes for products of every size over the years, and I always start new engineers with this exact exercise. It teaches normalisation, data structures, ranking and the limits of “just loop over everything” in one small, familiar problem.

The pipeline in one picture

Whatever the app, the path from keystroke to list looks about the same.

Let us walk through the stages in order, starting with the most naive version that works, because the way it fails shows you why each later trick exists.

Step 1: clean up what people type (normalisation)

Before any matching happens, both the typed text and the stored names need to be put into the same shape. People type “jose” for José, they type in lower case, and they put dots and dashes into names such as “Anne-Marie” or “O’Brien”. If you compare raw text, none of those match.

So the first stage lowercases everything, strips accents, replaces punctuation with spaces and splits the name into words. That is called normalisation, and it is the unglamorous step that makes the rest work. Skipping it is the number one reason homemade search feels “broken.”

Below is a first version of the whole search in about twenty lines. It normalises, then checks every contact. A contact matches when every word you typed is the beginning of some word in the name.

import unicodedata, re

def normalise(text):
    """Lowercase, strip accents, turn punctuation into spaces."""
    text = unicodedata.normalize("NFKD", text)
    text = "".join(c for c in text if not unicodedata.combining(c))
    return re.sub(r"[^a-z0-9 ]+", " ", text.lower()).split()   # list of words

def linear_search(contacts, query):
    """Slowest idea that works: look at every contact on every keystroke."""
    q = normalise(query)
    hits = []
    for cid, words in contacts:                  # contacts = [(id, [words...]), ...]
        # every typed word must be the start of some word in the name
        if all(any(w.startswith(t) for w in words) for t in q):
            hits.append(cid)
    return hits

This already behaves like a real contact search. Type “sh” and you find both Onam Sharma (the surname starts with sh) and Shalini Rao (the first name does). Type “on sh” and only Onam Sharma remains, because each typed word must begin some word in the name. Matching at the start of any word is what makes phone searches feel natural: you can type the first or the last name, in any order.

Step 2: watch the results shrink as you type

Here is something satisfying to see. I generated 5,000 made-up contacts (random first and last names) and ran the search above while “typing” the name anit, one letter at a time. My test names lean heavily towards names beginning with A, so the early numbers are larger than a real address book would give, but the shape is what matters.

This shrinking is the whole reason search-as-you-type works so well. The first letter does the least work and returns the longest list, which the phone only needs to display the top of. Every next letter cuts the list further, and by the fourth or fifth letter you are usually looking at a handful of names.

It also hides a second, very practical trick. Every result for “ani” is guaranteed to also be a result for “an”, because anything starting with “ani” also starts with “an”. So instead of searching all contacts again, you can search only the list you already have. I counted the name checks for typing anit across 10,000 contacts: scanning everything on every keystroke took 40,000 checks, while reusing the previous results took 13,852. That is about two-thirds fewer, for a change of a few lines of code.

Step 3: stop scanning, start looking up (the index)

The scan-and-reuse approach is fine for a thousand contacts. But it still touches every candidate on the first keystroke, and the cost grows with the size of the list. Real search systems avoid scanning entirely. They do the hard work once, ahead of time, and build an index, which is a structure designed to answer one specific question quickly. For “which words start with these letters?” the classic answer is a trie.

What is a trie?

A trie (said “try”) is a tree where each step down spells one more letter. All words that share a start share the same path. To find everything starting with “ani”, you walk three steps down and you are standing on the answer: every contact reachable from that spot begins with those letters. You never look at the other thousands of contacts at all.

The cost of a lookup depends on the length of what you typed, not on how many contacts you own. A person with 100 contacts and a person with 100,000 both pay the same few steps for “ani”. That is the property that makes it scale.

Here is a compact version. In this one, every node remembers the set of contacts passing through it, so reading the answer is instant:

class Trie:
    """Every node remembers which contacts pass through it."""
    def __init__(self):
        self.root = {}
    def add(self, word, cid):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
            node.setdefault("#", set()).add(cid)  # '#' holds contact ids
    def prefix(self, text):
        node = self.root
        for ch in text:
            node = node.get(ch)
            if node is None:
                return set()
        return node.get("#", set())

def build(contacts):
    t = Trie()
    for cid, words in contacts:
        for w in words:
            t.add(w, cid)
    return t

def trie_search(t, query_words):
    sets = [t.prefix(w) for w in query_words]
    return set.intersection(*sets) if sets else set()

The trade-off is memory. The trie stores extra information so lookups are fast, which is the oldest bargain in computing: spend space and preparation time to buy speed.

A simpler cousin: the sorted list and binary search

If a trie sounds like more machinery than you want, there is a leaner way to get the same effect. Keep every word in one alphabetically sorted list. All words starting with “ani” sit together in one block, because they sort together. Use binary search to find where that block begins and ends, which takes only about seventeen steps even for a hundred thousand words. If you read our article on heaps and sorted arrays, this is the same “sorted array” idea put to a different job. It uses less memory than a trie and is easier to write, and it is a perfectly good choice.

The numbers: how much faster is an index?

I built all three versions (scan, sorted list with binary search, and trie), checked that they return identical results on 500 random queries, and then timed them. The test is typing the four letters anit, taking the best of five runs, with different address book sizes. These figures come from Python on a cloud machine, so a real phone running compiled code will be quicker in absolute terms. What matters is the ratio.

Look at the first row of the table. With 1,000 contacts, every method finishes in a few milliseconds or less, and nobody would notice a difference. That is the honest takeaway: for a normal-sized address book, even the naive scan is fast enough. The index only earns its keep as the data grows. At 100,000 entries the scan needed about a third of a second to answer four keystrokes, which is long enough to feel sluggish, while the trie needed about a millisecond.

Step 4: searching by phone number

Name search matches the start of words. Number search needs different rules, because people remember numbers differently. They recall the last four digits, or the number without the country code, or they type it with spaces and dashes that were never stored.

The standard solution is to normalise numbers the same way we normalised names. Strip everything that is not a digit, and maybe drop a leading country code such as +91, so that “+91 98765-43210”, “098765 43210” and “9876543210” all become the same string. Then, instead of matching only at the beginning, you let the typed digits match anywhere in the number, or at the end for the “last four digits” habit.

Because digits have only ten possible characters, a similar trie or sorted index works well. For suffix searching, you can index the reversed number so “last four digits” becomes an ordinary prefix lookup.

Step 5: put the most likely person first (ranking)

Finding matches is only half the job. If typing “sha” returns thirty people in alphabetical order, the one you wanted may be on the third screen. So the list has to be ranked.

The idea is to give every match a score from several signals, then sort by score. The signals I always start with are: how well the text matches (the whole name starts with it, a word starts with it, or it appears in the middle), whether you marked the person as a favourite, and how often or how recently you contact them.

from norm import normalise

def score(contact, query):
    """Higher is better. contact = dict(name, favorite, calls)."""
    words = normalise(contact["name"])
    q = normalise(query)
    s = 0
    if " ".join(words).startswith(" ".join(q)):
        s += 100                      # the whole name starts with what you typed
    elif all(any(w.startswith(t) for w in words) for t in q):
        s += 60                       # every typed word starts some word in the name
    elif all(t in " ".join(words) for t in q):
        s += 20                       # typed text appears inside a word
    else:
        return 0
    s += 30 if contact["favorite"] else 0
    s += min(contact["calls"], 50) * 0.5   # frequent contacts float up
    return s

contacts = [
    {"name": "Shalini Rao",   "favorite": False, "calls": 2},
    {"name": "Onam Sharma",   "favorite": False, "calls": 40},
    {"name": "Sharad Verma",  "favorite": True,  "calls": 12},
    {"name": "Ashwin Shah",   "favorite": False, "calls": 5},
    {"name": "Harsh Gupta",   "favorite": False, "calls": 60},
]
query = "sha"
ranked = sorted(((score(c, query), c["name"]) for c in contacts), reverse=True)
for s, name in ranked:
    if s: print(f"{s:6.1f}  {name}")

Running it for the typed text “sha” gives:

 136.0  Sharad Verma
 101.0  Shalini Rao
  80.0  Onam Sharma
  62.5  Ashwin Shah

Notice the order. Sharad Verma is first because his name starts exactly with “sha” and he is a favourite. Shalini Rao is next on pure match quality. Onam Sharma follows, as only the surname starts with “sha”, even though he is called often. Ashwin Shah comes last of the matches, and Harsh Gupta does not appear at all because “sha” never occurs in his name. The weights (100, 60, 20, 30 and the call bonus) are just numbers I chose to demonstrate. In a real product, teams tune them with usage data, and that tuning is the difference between a search that is merely correct and one that feels uncannily helpful.

Step 6: forgiving typos (fuzzy matching)

Thumbs are clumsy and names have many spellings. Is it Anita or Anitha? Sunita or Suneeta? Strict prefix matching treats any typo as a complete failure. Fuzzy matching asks a gentler question: how many small edits would it take to turn what you typed into this name?

The classic measure is edit distance, also called Levenshtein distance, which counts single-letter insertions, deletions and replacements. Here it is in a few lines:

def edit_distance(a, b):
    """Minimum single-letter edits (insert, delete, replace) to turn a into b."""
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i]
        for j, cb in enumerate(b, 1):
            cur.append(min(prev[j] + 1, cur[j-1] + 1, prev[j-1] + (ca != cb)))
        prev = cur
    return prev[-1]

names = ["Anita", "Amit", "Anil", "Ankit", "Anjali"]
typed = "Anitha"           # another common spelling of "Anita"
for name in sorted(names, key=lambda n: edit_distance(typed.lower(), n.lower())):
    print(f"{name:<7} distance {edit_distance(typed.lower(), name.lower())}")

The output:

Anita   distance 1
Amit    distance 3
Anil    distance 3
Ankit   distance 3
Anjali  distance 4

“Anitha” is one deletion away from “Anita”, so Anita comes first, and everything else is at least three edits away. A search that falls back to fuzzy matching only when the exact search finds nothing gives you the best of both: exact results are fast and clean, and typos still find someone.

One small warning from experience: in plain edit distance, swapping two neighbouring letters (typing “Aniat” for “Anita”) costs two edits, not one, even though it is the most common typing mistake. A variant called Damerau-Levenshtein counts a swap as one. Also, comparing your text against every contact is slow, so real systems use fuzzy matching sparingly, usually on a shortlist, or use clever indexes built for it.

A fun relic: the keypad dialer

Many phone dialers let you type digits on the number pad and show contacts whose names could be spelled with those keys. It is the old keypad letter layout (2 for ABC, 3 for DEF and so on) doing a modern job.

KEYS = {"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
LETTER = {ch: d for d, chars in KEYS.items() for ch in chars}

def to_digits(name):
    return "".join(LETTER[c] for c in name.lower() if c in LETTER)

for name in ["Anita", "Amit", "Anil", "Ankit"]:
    print(f"{name:<6} -> {to_digits(name)}")

typed = "26"                          # you pressed 2 then 6 on the dialer
matches = [n for n in ["Anita", "Amit", "Anil", "Ankit", "Rahul"] if to_digits(n).startswith(typed)]
print("typed", typed, "matches", matches)

Anita  -> 26482
Amit   -> 2648
Anil   -> 2645
Ankit  -> 26548
typed 26 matches ['Anita', 'Amit', 'Anil', 'Ankit']

Pressing 2 then 6 matches every name whose first letter lives on the 2 key and whose second letter lives on the 6 key, which is why Anita, Amit, Anil and Ankit all appear. Add a 4 and Ankit drops out, because its third letter, K, sits on the 5 key. Add an 8 and Anil drops out too, leaving Amit and Anita. Working a few of these by hand is a good way to check that you really understand the mapping.

The same idea in five real settings

This pattern appears far beyond contacts. Click a tab to see it in other places.

When the data is not on your phone: debouncing and races

Everything so far searched a local list, where each lookup takes microseconds. Things change when the search has to ask a server, such as a company directory with a million staff or a search box on a website. Now each keystroke could trigger a network request taking 100 to 500 milliseconds, and two new problems appear.

• Too many requests. Typing a seven-letter name could send seven requests in a second. The fix is debouncing: wait until the user pauses for a short time, often 150 to 300 milliseconds, before sending anything. The delay is barely noticeable, and the request count drops sharply.
• Answers arriving out of order. The reply for “an” might arrive after the reply for “ani”, and the screen ends up showing results for the wrong text. The fix is to cancel the old request, or to tag each request with a number and ignore any reply that is not for the latest one.

Phone contact lists are local, so they rarely need debouncing. A server-backed search box almost always does. Knowing which situation you are in is half the design.

Hard cases that break simple search

• Names in other scripts. A contact saved in Devanagari or Arabic script cannot be found by typing Latin letters unless the system stores a transliteration or the user switches keyboards. Many real apps index several forms of the same name.
• Prefixes in surnames. “McDonald”, “de la Cruz” and “Al-Farsi” do not split into words the way English names do. Treat the hyphen and the apostrophe thoughtfully.
• Accent rules differ by language. Stripping the dots from “ü” helps in French and Spanish but may be wrong in German searches, where “ue” is the usual substitute.
• Sorting order. The alphabet itself differs between languages. Sorting by raw character codes puts all capitals before all lowercase letters. Use a locale-aware sort.
• Duplicates. The same person saved twice with slightly different details should usually appear as one result.

Which approach should you choose?

Common mistakes when building search-as-you-type

• Skipping normalisation. Case and accent mismatches make good data look broken.
• Matching anywhere instead of at word starts. Typing “an” returns “Hannah” and “Joanna” before “Anita”, because they contain “an” in the middle. Prefer word-start matches and rank anywhere-matches lower.
• Not ranking at all. An alphabetical list of thirty matches is a correct answer and a poor experience.
• Rebuilding the index on every keystroke. Build once, update when contacts change.
• Doing the work on the main thread. Heavy searching on the thread that draws the screen makes the typing itself stutter.
• Forgetting empty results. Show something helpful, such as “no match” or a fuzzy suggestion, not a blank screen.

Test yourself

Tap a question to reveal the answer. The correct option is marked.

Frequently asked questions