Lecture: Algorithms: Searching, Sorting & Growth
Lecture script · about 15–20 minutes spoken · Week 13
Opening
Picture a biology major hunting for one sample ID in a freezer log, or a business student sorting a store's sales so the best sellers rise to the top. Both have a program that gets the right answer. This lecture asks how much work it does, and what happens to that work when the data doubles.
Here's a feeling you already have. You want page 87 of a thick printed book. You don't start at page 1. You open near the middle, see page 212, and flip back. A few flips later you're there. A friend who turned every page from the front would also get to page 87, but only after 86 page turns. Same answer. Wildly different work.
Let me connect this to what you've built. Week 5 gave you while loops, counters, and the off-by-one error. Week 6 nested one loop inside another. Week 7 gave you functions that return a value, Week 9 gave you lists, and Week 10 gave you the one-line swap and tuples. Every program in this lecture is made of those parts.
Here's the plan. We'll search a list two ways, count the work, and test a search at its edges. Then we'll sort a list, count that work too, and name the patterns of growth.
1. Check every item in turn
Imagine a teacher looking for one student's quiz in a stack of 30. The teacher starts at the top and checks each sheet until the right name appears. Nothing about the stack needs to be in order.
That method has a name: linear search, a search that checks the items of a list one at a time from the front until it finds the target or runs out of items. It works on any list, sorted or not. The target is the value a search is looking for.
Your reading log now keeps eight daily page counts, sorted from smallest to largest: 3, 8, 12, 15, 21, 27, 34, and 40. The course's linear search hands back two things together as a tuple: the index where it found the target, and how many comparisons it made.
Search for 21. The function compares 3, then 8, then 12, then 15, then 21. That's a match at index 4, after 5 comparisons, so the program prints the tuple 4, 5. Search for 3, and the very first check matches: index 0, after 1 comparison. Now search for 22, which isn't in the list. The function checks all 8 items, finds nothing, and hands back negative 1 for the index, with 8 comparisons. Negative 1 is the "not found" signal, the same one that find gave you for strings in Week 11.
It's tempting to think a search that finds nothing did no work. In fact a missing target is the most expensive case of all.
Pause and try this. Linear search looks for 40 in the reading log's eight page counts. How many comparisons does it make?
Count the items from the front, one at a time.
Here's the answer. It makes 8 comparisons, because 40 is the last item, at index 7, and every item before it gets checked first.
Linear search reads the stack from the top.
2. Count comparisons, not seconds
Two friends race to find a name in the same list, one on a new laptop and one on an old phone. The laptop wins. That proves nothing about the method, because the faster machine would win with the worse method too.
So we need a measure that doesn't depend on the machine. That measure is a comparison counter: an accumulator that adds one each time a search or sort compares two values, so the program reports how much work it did as a count that is the same on every machine. You've built this before. It's the Week 5 accumulator, one line that adds 1 to a name called comparisons, placed right where each comparison happens.
Here's the course's head-to-head. Take the sorted list of the whole numbers 1 to 16 and look for 13. Linear search checks 1, 2, 3, and on up to 13, so it needs 13 comparisons. Binary search, which we'll unpack in a moment, needs 4. Both find 13 at index 12. Look for 16, the last item, and it's 16 comparisons for linear search and 5 for binary search.
A clock reads differently on a different machine, or even on the next run. A count never changes, so this course never grades a timing.
Pause and try this. Linear search and binary search both look for 16 in the list 1 to 16. Which count belongs to which search?
Think about which one starts at the front.
Here's the answer. Linear search makes 16 comparisons and binary search makes 5. Linear search walks every item up to the last one, and binary search starts in the middle.
A count travels; a clock stays home.
3. Halve the list
Back to the printed book. You open in the middle. If your page is higher, you never look at the first half again. If it's lower, you never look at the second half. Each look throws away half of what's left.
That's binary search: a search on a sorted list that compares the target with the middle item and throws away the half that cannot hold it, repeating until it finds the target or no items are left.
The program keeps two names for the ends of the part still in play. Lo is the lowest index that could still hold the target, and hi is the highest. The middle index is lo, plus hi minus lo, floor-divided by 2. The loop keeps going while lo is less than or equal to hi.
Let's trace the search for 21 in the reading log. There are 8 items, so lo starts at 0 and hi at 7. The middle index is 3, which holds 15. Since 15 is less than 21, the target can only be to the right, so lo moves to 4. The new middle index is 5, which holds 27. Since 27 is more than 21, the target can only be to the left, so hi moves to 4. Now lo and hi are both 4, the middle index is 4, and it holds 21. Found, after 3 comparisons.
The reading log's Week 13 stage runs this search three times and prints 4, 3 for the target 21, then 0, 3 for the target 3, then negative 1, 3 for the missing 22.
Pause and try this. On the first pass of the search for 21, what are lo, hi, and mid?
Start from the two ends of an eight-item list.
Here's the answer. Lo is 0, hi is 7, and mid is 3. The middle index is 0 plus 7 minus 0, floor-divided by 2, which is 3, and index 3 holds 15.
Look in the middle, then throw half away.
4. Sort first
Now shuffle the book's pages. Open to the middle and see page 212. Is page 87 to the left? You can't know. Halving needs order.
That rule has a name. A precondition is something that must already be true before an algorithm runs for it to work correctly, and binary search's precondition is that the list is sorted.
The pinned run breaks it. The list holds 27, 8, 40, 3, and 15, in that order. The search for 3 checks the middle item first, which is 40. Since 40 is more than 3, it throws away everything to the right, including the 3 itself. The program prints negative 1, which says not found, about a number that is sitting right there in the list. No error appears. That's a logic error: the program ran and printed the wrong thing. Sort the list first and search again, and the program prints 0, because 3 is now the first item.
Binary search isn't always faster, either. The 3 at the front of the reading log took binary search 3 comparisons and linear search 1. On a tiny list, or for a target near the front, the plain method can win.
Pause and try this. Why did binary search report negative 1 for a 3 that was in the list?
Think about which half it threw away first.
Here's the answer. The list was not sorted, so when the search saw 40 in the middle and went left, it threw away the half that held the 3.
Halving needs order.
5. Test the ends
A recipe that works for one tray of cookies can still fail for a single cookie or for a whole bake sale. A careful baker tries the small case and the large case, and a careful programmer does the same.
Binary search has a famous history. Bentley's Programming Pearls, from 1986, records that the first binary search was published in 1946, and that the first one correct for every list length didn't appear until 1962. Much later, Bloch's note in 2006 reported that a widely used library's binary search had carried a bug in its middle-index line for about nine years. That line added the two ends before halving them, and in a language with a size limit on whole numbers, the sum could grow past it. Python's integers never overflow, but the course writes the safe form anyway.
The worst case is the input of a given size that makes an algorithm do the most work. The correct search on the reading log finds 3 in 3 comparisons and 40 in 4, and it reports negative 1 for 2 and for 41.
Now change one line. Start hi at the length of the list instead of the length minus 1. The search for 21 still prints 4, which is exactly why the bug survives a quick test. But the search for 41 keeps moving right until mid reaches 8, and the list only has indexes 0 to 7. The program stops with an IndexError, which you read on the last line of the error.
A chatbot's binary search is a claim. Your runs on both ends, and on a value missing from each side, are the evidence.
Pause and try this. Which four targets would you run to test a binary search on the reading log?
Think first item, last item, and one missing value on each side.
Here's the answer. Run 3, 40, 2, and 41. Those test the first item, the last item, a value below every item, and a value above every item.
Test both ends and one missing value on each side.
6. Sort pass by pass
Picture lining up five friends by height for a photo. Walk the shortest person to the first spot, then the shortest of those left to the second spot, and keep going until everyone is placed.
That's selection sort, a sorting algorithm that, on each pass, finds the smallest item not yet in place and swaps it into the next position, so the sorted part at the front grows by one item per pass.
In code it's a nested loop from Week 6. The outer loop picks the place to fill. The inner loop runs to completion on every pass of the outer loop, scanning everything after that place to find the smallest item. Then the one-line swap from Week 10 trades the two items.
The course's pinned trace sorts the list 27, 8, 40, 3, 15. On pass 1 the smallest item is 3, so 27 and 3 trade places, and the list becomes 3, 8, 40, 27, 15. On pass 2 the smallest of what's left is 8, already in place, so the list doesn't change. On pass 3 the smallest is 15, so 40 and 15 trade places, and the list becomes 3, 8, 15, 27, 40. Passes 4 and 5 find their items already in place. The last pass always does, because a single remaining item is already where it belongs.
A pass that changes nothing was not skipped; the inner loop still scanned every remaining item.
Pause and try this. After pass 1, the list reads 3, 8, 40, 27, 15. Which two items trade places on pass 3?
Find the smallest of the three items still unplaced.
Here's the answer. The 40 and the 15 trade places. The smallest of 40, 27, and 15 is 15, and it swaps into index 2.
Find the smallest, swap it forward, repeat.
7. Count the sort's comparisons
Back to the photo line. With five friends, the first scan compares four people, the next three, then two, then one. That's 10 comparisons.
The course's pinned count runs selection sort on 5, 10, and 20 items and prints 10, 45, and 190. Those follow one formula: n times n minus 1, divided by 2, where n is the number of items. Five times four, divided by 2, is 10. Ten times nine, divided by 2, is 45. And 20 times 19, divided by 2, is 190.
Look at what doubling did. From 10 items to 20, the work went from 45 to 190, about 4.2 times as much. Twice the list cost about four times the comparisons.
Here's a surprise: an already sorted list of five items still takes 10 comparisons. The inner loop has no way to stop early, so selection sort does the same work whatever order the items start in.
Pause and try this. Selection sort makes 45 comparisons on 10 items. Roughly how many does it make on 20?
Doubling the list does more than double the work.
Here's the answer. It makes 190 comparisons, about four times as many. The formula gives 20 times 19, divided by 2, which is 190.
Double the list, quadruple the sort.
8. Name the growth
Double the distance to class, and you double the walk. Double a club where everyone signs a card for everyone else, and the cards roughly quadruple. Looking up one friend on your phone takes the same moment however many contacts you have.
A growth class is the pattern by which an algorithm's step count rises as its input grows. Big-O is a way of naming an algorithm's growth class that describes how the step count grows with the input size n, rather than giving the exact count.
This week shows four classes. Reading the item at index 4 of the reading log, the 21, is one step at any length: that's constant time, big O of 1. Binary search adds about one step each time the list doubles: that's logarithmic time, big O of log n, about log base 2 of n steps. Linear search's worst case doubles when the list doubles: that's linear time, big O of n. Selection sort's comparisons roughly quadruple when the list doubles: that's quadratic time, big O of n squared.
The doubling run makes it concrete. For lists of 8, 16, and 32 numbers, linear search needs 8, 16, and 32 comparisons to find the last item, while binary search needs 4, 5, and 6. In the number game from 1 to 100, halving never needs more than 7 guesses.
Big-O names the growth, not the count. Finding 13 took 4 comparisons and finding 16 took 5, and both are logarithmic time. Merge sort and quicksort, faster sorts, come later in a second course.
Pause and try this. Linear search goes 8, 16, 32 as the list doubles. Binary search goes 4, 5, 6. Name each growth class.
Ask what each doubling of the list does to the count.
Here's the answer. Linear search is linear time, because each doubling doubles the count. Binary search is logarithmic time, because each doubling adds about one step.
Big-O asks what happens when the list doubles.
Closing
Let me pull it together. Linear search checks items from the front, so 21 took 5 comparisons and the missing 22 took all 8. Counting comparisons gives a measure that is the same on every machine: 13 against 4 for the target 13. Binary search halves a sorted list, and it found 21 in 3. It needs a sorted list, or it can miss a present item, the way it missed the 3. Test a search on both ends and past both ends, because starting hi one too high raised an IndexError. Selection sort swaps the smallest remaining item forward on each pass. Its comparisons went 10, 45, and 190, so doubling the list roughly quadrupled the work. And Big-O names the growth class: constant, logarithmic, linear, or quadratic.
Next in this module come the slide deck, the Readings and Resources page, the lecture tutorial, the practice set, the quiz, the discussion, and the Coding Lab. Then, in Week 14, Recursion, you'll write a function that calls itself, and the halving behind binary search is one of the places where that idea feels natural.
Built with The Course Maker · samples.thecoursemaker.com