Module 22: Loops and Algorithms
Searching
🏠The everyday picture
Finding a name in a pile of unsorted forms means checking every one. Finding it in a phone book, sorted alphabetically, means opening near the right letter and narrowing down.
📘What it really is
-
Linear search: check each item in turn until you find a match. Simple, works on any list. That's what
find,filter,includesandindexOfdo. -
Search by text usually means:
- ignoring case: compare
name.toLowerCase()withquery.toLowerCase(); - matching part of a word:
name.toLowerCase().includes(query); -
trimming spaces from what the person typed:
query.trim(). -
Binary search: on a sorted list, look at the middle; if the target is smaller, throw away the top half, otherwise the bottom half; repeat. A million items take about 20 steps instead of a million.
-
Lookup by id: for frequent lookups, build a Map (a ready-made index) once:
const byId = new Map(products.map(p => [p.id, p]));
byId.get("P003");
Getting an item from a Map is instant, however many items there are.
🖱️Try it
Write a function searchProducts(query) that returns every product whose name contains the query, ignoring
case and extra spaces. Test it with "pen", " PEN " and "xyz". Then build a Map by id and look up two products.
✅Quick check
A search for "pen" misses "Pen Stand". What's the likely bug?
Show the answer
The comparison is case-sensitive. Convert both to lower case before comparing.
Why can binary search only be used on sorted data?
Show the answer
It relies on knowing which half the target must be in, which is only possible if the data is in order.