Lesson 9 of 12 · 34 min · Grades 9–12
Search and sort
Finding a roll number in a messy register is linear search. Sorting times lets a coach pick medalists. You will use list.sort and pandas sort_values in production; implementing linear search once teaches why databases have indexes.
Roll-number search
Scan a list; sort a copy.
You will be able to
- ✓ Linear search with a flag
- ✓ Use sorted() for an ordered copy
Linear search
Walk until you match. Worst case you scan everyone — fine for a class list, costly for millions of rows. That cost is why search engines do not use a Python for-loop over the internet.
A boolean found starts False and becomes True on match. Printing Found True/False is a tiny test you can extend to return the index.
sorted returns a new list
sorted(xs) does not destroy xs. Keep the original if you still need arrival order. Sorting numbers is obvious; sorting dicts needs a key function in full Python (sorted(rows, key=lambda r: r["time"])).
Words that matter
- Linear search
- Check items one by one until you find a match.
- sorted
- Built-in that returns a new ordered list.
Common mistakes
Avoid: Assuming the list is already sorted.
Do this: Search unsorted data linearly, or sort first if you will search many times.
Example program — Find a roll number
Change target to a missing id.
Edit the example, press Run, then Build if you want a compile check.
build
Press Build to compile.
Your turn — Is 8 in the list?
nums = [3, 8, 1]. Print Found True if 8 is present.
Edit the example, press Run, then Build if you want a compile check.
build
Press Build to compile.
Self-assessment
Check your understanding before you mark the lesson complete.
Progress is stored in a browser cookie on this device.