When we closed module 5 we said that EasyTask's success brought with it the best kind of problem: once Alba Studio's agenda holds two hundred tasks in tasks.json, "find the one for the Vidal account" stops being trivial. So far we have used in, .index() and set membership as black boxes: they work, and we never asked how. This lesson opens the first of those boxes.

Searching is, by a wide margin, the most frequent operation in any program that handles data. Here you will learn the three families of techniques that exist —linear search, binary search and key lookup—, what each one demands, what it costs and when to choose it. We will implement them by hand to understand them from the inside, with the same honest moral as always: in production you use the language's own tool.

1. What searching means and what it returns
2. Linear search: the reference algorithm
3. Step-by-step trace of a linear search
4. Searching with a condition: the callback returns
5. Finding every match
6. Binary search: the idea of discarding half
7. Binary search: implementation and trace
8. Linear versus binary
9. Key lookup: dictionaries and sets
10. Inverted index: preparing the search
11. EasyTask v0.12: three ways to locate a task
12. Common mistakes and tips
13. Exercises
14. Conclusion

"Searching" looks like one single thing and is really three different questions, and mixing them up is the beginner's first mistake:

In a list of numbers the three almost always coincide. In our agenda —a list of dictionaries— the difference is enormous: knowing that a task of Nuria's exists is no help at all if I want to change its priority; for that I need the dictionary, or at least its position.

And there is a fourth decision: what happens when nothing is found. The three usual conventions are returning -1 (a tradition inherited from C and Java), returning None (the idiomatic choice in Python when you return an element) or raising an error, which is what .index() does with its ValueError. We will use -1 for positions and None for elements. Whatever the convention, document it in the docstring and stay consistent across the whole program.

Linear search (or sequential search) is the simplest algorithm there is: look at the elements one by one, from the start, until you find the one you want or run out of collection. It demands absolutely nothing of the data: sorted or unsorted, in a list, in a file or on a tape.

Translated into Python over our agenda, with the enumerate from 05-01 so we have position and element at the same time:

Three details make this code good. The early exit with return: the moment it finds the task, the function ends; if we stored the result in a variable and carried on looping, in an agenda of 200 tasks we would look at 199 elements too many. The return -1 is outside the loop, aligned with the for: you only get there when the sweep has finished without finding anything; placed inside, the function would return -1 on the first pass that did not match. And the comparison is ==, not in: it demands an exact match, and we will see the "contains" variant in section 4.

The two functions are identical except in what they return, the position or the element. And remember the aliasing from 05-01: what the second one returns is the very same dictionary that lives in the list, so find_task(agenda, "Book fair poster")["priority"] = "low" really does modify the agenda. It is the mechanism choose_task has been relying on since v0.10.

Let us run the desk check from 01-05 over this Alba Studio agenda:

We trace two cases at once: A, searching for "Vidal logo", which is there; and B, searching for "Summer flyer", which does not exist.

Case A finishes in three comparisons and position 3 is never looked at: that is the effect of the early exit. Case B needs four, that is, all of them. And there you have the module's first lesson about cost, read straight off the table. Best case: the element is first, one comparison. Worst case: it is last or it is not there, as many comparisons as elements. Average case: half the elements. Hold on to the important detail: the worst case of a linear search is finding nothing, so a program that often searches for things that do not exist is in the worst possible scenario for this algorithm.

The functions above only know how to search by exact title. If Marta wants to search by assignee, by priority or by "titles containing the word fair", do we write one function per case? No: we apply the callback pattern from 04-05, and instead of the value to compare, the function receives the check in the form of a function.

The skeleton of the sweep is supplied by find_if; the decision about what counts as "found" is supplied by the caller. The third line uses the string in from 05-02 —"contains"— and .lower() so case is ignored, which is what any user expects; the fourth combines two conditions without find_if ever noticing. Python ships this idea built in, via next and a generator expression:

It reads as "the next element of the agenda whose assignee is Nuria, or None if there is none". Without that second argument, next raises an error when there are no matches. It is the idiomatic, lazy form —it stops sweeping the moment it finds a match, just like our return— and the one you would use in a real project. find_if exists so you can see there is no magic underneath: it is a for with an if.

Sometimes you do not want the first one, you want all of them: "every task of Luis's", "every high-priority one". The algorithm changes in one essential point: there is no early exit, because the whole collection has to be examined.

The comprehension is the preferred option for readability. And watch that last line: if all you need is how many there are, count directly instead of building a list you were going to throw away.

If the data is sorted, you can do something far better than looking one by one. Think about how you look a word up in a paper dictionary: you do not start at A, you open it in the middle, see which letter you have landed on and discard half the book in one go. That is the binary search algorithm, and its requirement is non-negotiable: the collection must be sorted by the same criterion you are searching on. If it is not, binary search does not raise an error, it gives wrong answers, which is far worse.

Over this sorted list of Alba Studio job codes —[102, 118, 134, 156, 170, 189, 203, 240], positions 0 to 7— we search for 170:

Three comparisons for eight elements, against the five a linear search would need. The difference looks modest here; with a million it is abysmal, and we will see it numerically in section 8.

The algorithm keeps three variables: left and right delimit the chunk where the value could still be, and mid is the position examined on each pass.

Four points where this algorithm breaks, and they have to be understood precisely:

• while left <= right, with the equals. When the two coincide there is still one element left to look at, and it has to be looked at. With a bare < you would miss exactly the values that end up alone at the end of a chunk.
• (left + right) // 2 uses the integer division from 02-02: if the sum is odd it rounds down. Which way it rounds does not matter, as long as the chunk shrinks on every pass.
• mid + 1 and mid - 1, never a bare mid. We have already checked that values[mid] is not the target, so it gets discarded too. With left = mid, the chunk stops shrinking once two elements are left and the program hangs in an infinite loop.
• The chunk is halved on every pass, and that is why the loop always ends: either it finds the value, or left eventually overtakes right.

Let us trace two searches over the list of codes, one row per pass of the while: 170, which is there, and 150, which is not.

Look at the two third passes: in both, left and right hold the same value, the loop does run and examines the last candidate. Only afterwards does left overtake right and the loop end. It is the best demonstration that the <= is not a cosmetic detail.

There is also a recursive version of this algorithm, shorter and for many people more elegant, which we will write in Recursion once we have the tool. And, as always, Python already ships this: the bisect module of the standard library implements binary search in C, and its bisect.insort(my_list, value) function inserts while keeping the order. In production you use bisect; this implementation is for understanding what it does inside.

The numbers come from a simple rule: every pass of the binary search halves the pending chunk, so doubling the data adds a single comparison. Going from a thousand to a million elements multiplies the linear search's work by a thousand and adds ten comparisons to the binary one; we will put the formal name to that difference in Efficiency and Big-O Notation. But the table also warns about the small print: sorting costs. If you are going to search an unsorted list just once, sorting it so you can use binary search works out more expensive than sweeping the whole thing. Binary search pays off when the collection is already sorted or when you are going to search many times.

That leaves the fastest of the three techniques, the one you have been using since 05-03 without knowing how it works. Asking "Marta" in team or reading record["role"] sweeps nothing and compares nothing: it finds the data in one jump, whether the dictionary has ten keys or ten million. The mechanism is called a hash table, and the intuitive idea, without going into detail, is this: Python applies a mathematical function to the key —the hash function— which always turns it into the same number; that number tells you which slot of an internal table the key-value pair lives in; and to search, the calculation is repeated and you go straight to that slot, sweeping nothing.

That is also the explanation for the requirement from 05-03: dictionary keys and set elements must be immutable. If you used a list as a key and then modified it, its hash would change, the computed slot would be a different one and the data would sit somewhere nobody is going to look. The practical summary is emphatic:

We anticipated the operational conclusion back in 05-03 and now you know why: if your program does many membership checks on a collection, that collection should be a set or a dictionary, not a list. The price is extra memory and losing insertion order as a search criterion.

Here comes the idea that turns all of the above into a design decision. If Marta is going to ask "what does Luis have?" fifteen times a day, sweeping the whole agenda fifteen times is absurd: better to sweep it once and build a dictionary that answers instantly. That structure is called an inverted index: instead of going from the task to its assignee, it goes from the assignee to their tasks.

The if name not in index: index[name] = [] pattern is the same "first time" from 05-03, and it also fits on one line as index.setdefault(name, []).append(task). index.get("Luis", []) returns an empty list if that person has nothing, avoiding the KeyError.

This is a trade-off: we spend memory and one preliminary sweep so that later queries are immediate. It pays off when you query a lot and modify little; it does not pay off when the agenda changes non-stop, because the index goes stale the moment a new task is registered. It is the first appearance of the time-memory trade-off, which we will study by name in 06-04.

We add to the program a search option that uses all three techniques depending on the case: by exact title when Marta knows what she is after, by contained text when she only remembers one word, and by assignee with an index when she wants the workload split. The menu grows to eight options.

Design decisions worth pointing out:

• find_if and find_all know nothing about tasks. They take the condition as a callback, so they work for any collection of dictionaries; all the specific logic lives in the lambdas inside search_menu.
• search_menu is the only one that talks to the user, honouring the separation between input/output and logic from 04-04. The search functions print nothing, and the three branches converge on a single matches list that is displayed the same way in all three cases. On top of that, the text search lowercases both sides, so "vidal", "Vidal" and "VIDAL" all find the same thing.
• The index is built inside branch 3 and thrown away on the way out. That is deliberate: the agenda changes between one query and the next, and an index stored in a global would go stale. With twenty tasks, rebuilding it costs a blink.

There is no binary search in EasyTask, and that is a conscious decision: the agenda is not sorted by title, and sorting it just to be able to search would cost more than sweeping it. With twenty tasks, linear search is the right answer.

Putting the "not found" return inside the loop. It is the number one mistake of this lesson: the function returns -1 or None on the first pass that does not match, without looking at the rest. That return goes outside the for, at the same level as it.

Forgetting to check the result. If find_task returns None and you write task["priority"], you get TypeError: 'NoneType' object is not subscriptable. Always check with if task is not None: before using what came back. And using binary search on unsorted data does not fail with an error, it fails with a wrong result: it says an element is not there when it is. If your function requires order, say so in the docstring. Writing left = mid instead of mid + 1 stops the chunk from shrinking and hangs the program in an infinite loop; if your binary search freezes, look there first.

Confusing == with in when searching text. t["title"] == "fair" only finds a task called exactly that; "fair" in t["title"] finds every task containing it.

Tip: normalise before comparing. Apply .strip().lower() to both sides when you search text typed by a person: a trailing space is invisible and breaks the comparison.

Tip: in production, use the language's tool. in, .index(), next(...), a comprehension, a dictionary or bisect are written in C, tested by millions of programs and faster than any loop you write. These implementations exist so you understand what they do inside and know which one to pick, not to be copied into your project.

Over the sorted list [2, 5, 9, 14, 21, 30, 44, 51, 68] (positions 0 to 8), trace in a table the binary search for the values 44 and 7, giving on each pass left, right, mid, the value examined and the action. State how many comparisons each search needs and how many a linear search would have needed.

Write three functions over the agenda (list of dictionaries with title, assignee, priority, days, completed):

• first_urgent(agenda): returns the first pending high-priority task, or None.
• pending_for(agenda, name): returns the list of that person's pending tasks, ignoring case.
• has_bottleneck(agenda): returns True if somebody has more than three pending tasks. It must rely on an index, not on a nested loop.

Write index_by_priority(agenda) returning a dictionary with the keys "high", "medium" and "low" —all three always present, even if some are empty— and, as the value, the list of titles of the pending tasks with that priority. Then write report(index) that prints each priority with its number of tasks and its titles.

Solution 1.

Two comparisons for the 44 (a linear search would have needed seven) and three for the 7 (a linear search, all nine of the full sweep, because it is not there). Notice the asymmetry: binary search takes almost the same whether it finds the value or not, while failure always costs a linear search the maximum.

Solution 2.

has_bottleneck sweeps the agenda just once building an index of counts, instead of sweeping it once per team member. With three people the difference is irrelevant; with three hundred, it is the difference between a usable program and an unusable one. any returns True the moment it finds a value that satisfies the condition and stops looking: it is the early exit from section 2, already built into the language.

Solution 3.

The key is the first line: {p: [] for p in PRIORITIES} is a dictionary comprehension that creates the three keys up front using the PRIORITIES constant. Thanks to that, the loop can do index[...].append(...) without checking anything, and report walks the priorities in their logical order —high, medium, low— instead of the order they happened to appear in the agenda. Choosing the right structure simplifies the code that comes after it.

Searching is not one operation, it is three questions: whether it exists, where it is and which one it is; plus a fourth decision, what to return when there is nothing (-1, None or an error). Linear search sweeps one by one with an early exit via return: it demands nothing of the data, finds in a single comparison in the best case and has to sweep everything in the worst, which is precisely when the element is not there. Turned into a higher-order function with a callback, the same function searches by title, by assignee or by contained text; and without the early exit it becomes the search for every match, which in Python is written as a list comprehension.

Binary search swaps sweeping for discarding: it demands sorted data and on every pass splits the problem in two, so a million elements are resolved in twenty comparisons. Its three traps are the while left <= right, the (left + right) // 2 and the mid + 1 / mid - 1 that guarantee the chunk shrinks. And key lookup in dictionaries and sets beats both of the above thanks to the hash table, which computes the slot instead of comparing; hence the requirement that keys be immutable. When a query repeats a lot, it is worth paying for one sweep and some memory to build an inverted index. And in production, always, the language's own tool: in, .index(), next, a comprehension, a dictionary or bisect. EasyTask reaches v0.12 and Marta can now question her agenda. But binary search has gone unused for a concrete reason: the agenda is not sorted, and sorting is exactly what we have been delegating to sorted without asking. In Sorting Algorithms we will open that second black box: what sorted does inside, what it means for a sort to be stable and why sorting is the most profitable operation in the whole course.